Most of the newest devices have built in GPS, but the carriers don't necessarily activate it in the custom ROM's. AT&T does. Sprint has stated (and the ROM has been leaked, so likely true) that they will be releasing an upgrade to the Touch. I think they already did for the Mogul.
Verizon is tight lipped about it so far, but their new "any device" certification policy means that we'll probably see availability on their network soon too (and again, the leaked and custom kitchen ROM's available can add it even to a Verizon device).
I haven't been willing to risk wrecking my VX6900 yet with a hacked ROM but I do have Bluetooth GPS that works fine. Supports NMEA and every program I have tried it with works fine.
Alan