I didn't lose any weight during my first 30 days, but I did lose 1-2 dress sizes. I was not overweight to start. I also did Crossfit a few times a week during that time.
I didn't count calories, fat, or carbs. I just followed general Paleo recommendations blindly. I found that counting all those carbs and calories just overcomplicated it for me. So, in short, no dairy, no grains, no legumes and only "good" fats (avocado, coconut oil, grapeseed oil, EVOO, etc.). I had the occasional sweet potato after a particularly hard workout, maybe twice a week. I struggled with sugar and had the occasional piece of chocolate.
I guess I feel that if you don't have a serious metabolic disorder and you're not chronically ill, counting carbs isn't particularly useful at all. I think the issue is the digestive/metabolic issues associated with grains/dairy/legumes, not the amount of carbs you take in. I associate carb reduction with Atkins, which I don't feel is as healthy or successful as paleo.
Also - i drank water and black tea mostly. Sometimes I threw some berries or lemon into my water to break it up.