Here's what I ended up doing,
Turns out, you don't need to worry about cookies, Android will manage them for you. All you have to do is make sure you use the same http client for all your requests
private static DefaultHttpClient httpClient = new DefaultHttpClient();
So, I created a singleton class and put my httpClient there.
Creating a new httpClient every time is like closing your browser and opening it again on the computer.