First tried (many years ago) laptop, USB GPS and something like Route 69, or something. This was before the smaller units became popular / affordable.
Then bought IPAQ & Destinator 2. D2 was okay, but I couldn't get Euro maps for it (after I bought it, they released D3 - aftersales support suggested I upgrade for £100 before being allowed to buy new maps).
Replaced D2 with TomTom 3 (or is it 2?, nothing on the box!), also for the IPAQ. Then the wife bought me the Euro maps. Served me well, but I have a blind spot for the PDA and after a few days the batteries are gone and I have to reinstall the application. Not ideal! Also - never carry the IPAQ with me so PITA when you accidentally get lost!
Now, got a Sony Ericsson 910i mobile phone - it's a symbian phone, and I run TomTom5 on that. Always have it with me, and it doesn't suffer like the IPAQ for removing applications when the battery runs low. I've obviously got a phone charger in the car, and a car windscreen mount kit, all I need now is a car-charger for the GPS unit (this is my weak spot atm) and I'm good to go.
For me, having the GPS integrated with the phone is the best option. Also kinda geek-cool when someone's asking in the pub about someplace (e.g. nearest rail station to a place - actual example) to whip out the phone and zoom into the area, pull up POIs etc.