Just starting a new thread in response to this:
freitasm: It would be better to start a new discussion - so I will answer here but if you need further clarification please open another thread.
If your PDA is Bluetooth-enabled any Bluetooth GPS would work fine. Holux makes some good ones, as well as Globalsat.
As for software, if you are in Australia, Tom Tom and CoPilot 7 both have Windows Mobile versions with Australian maps.
I'm in New Zealand, although for some reason my little flag avatar is Australian.
I read another discussion noting that TomTom doesn't have NZ maps, is that still the case?
I've also heard that Google maps won't plot your position directly from a GPS receiver, is that true?
Thanks for the help, I'm a little bewildered :)
Edit: I think googlwe maps requires mobile internet to work. If so, then my google maps question is moot :D