Ahhh, the weight question once again.
I asked a very similar question about a month ago. I've been sitting at 76kg for some time now, but I eat all the wrong kinds of foods. Full cream milk, Pizza, Pasta (Alfredo) pies and chicken burgers.
I tried going on a diet and guess what. I lost 500grams here, picked up 750grams there, lost 500grams here etc.
Decided to become a little more focussed, thanks to advice given by the very same people you are asking and had my body fat % taken. The result was actually more of an eye-opener than I anticipated as I was significantly less overweight than I expected.
Problem is, I used to do bodybuilding (many moons ago) and have too much muscle (for a cyclist) on my upper body and this is why I weigh so much.
I'm very active as you'll see from project creatine, so I inevitably burn more calories than I consume, so my weight stays down and my fat % is dropping. (I'm now at 7%)
My contribution is therefore the following:-
Make realistic goals. Don't just say I want to lose weight.
Measure yourself against those goals regularly. There is also some nice advice on Lance Armstrong's site. check out http://www.lancearmstrong.com/lance/online2.nsf/html/greenbook