Fox, forget root, fowler002 read the thread properly before even thinking about rooting

(I don't mean that to sound harsh to either of you, its just some friendly advice, it took me months to root my Nexus, I watched about 20 videos of the process on YouTube and read 10 or so guides, and a 6 year old could root a Nexus, the Desire is in a different league of complexity

)
"Root access" opens the phone up so ROM images do not need do not need to be "signed" by the manufacturer and so that you are given "superuser" permissions and generally gives access to parts of the OS not suitable for Joe Public - WiFi tether, control over the camera flash (To turn it into a torch) and the like.
Paul's method is a bit odd, I still really object to it, here's why:
Rooting
shouldn't change the ROM on the device, and as a result it shouldn't affect Sense, it is, essentially like swapping a Windows account from "standard user" to "administrator" for want of a better analogy. His method is more akin to creating a new user with administrator rights then deleting the original account and using the new one instead. It does the job, but its not exactly slick or simple. (Then again the first method may never be available on the Desire, it all relies on someone finding a simpler exploit in the code of the bootloader)
Paul's method roots the phone then flashes a new ROM onto the device and is explained as if its one step, and you must complete all of said step in order to root, and fowler002 this is where you might have gotten your wires crossed, depending on which ROM you've chosen to flash will depend on if you have Sense or not. There seem to be two basic ROM's out there atm. First is the Desire ROM with added shinny bits like WiFi tether and Apps2SD. The second is a direct port of Cyanogen's Nexus One ROM, which never had Sense, but is a much more serious restructuring of the underlying OS, giving huge performance gains, as well as adding the WiFi tether and Apps2SD
After you gain root access you will then be able to flash whatever ROM you want, including stock HTC ROM's, Vodafone ROM's (For warranty purposes, see below) and custom ROM's that streamline the OS as per Cyanogen et al. Some of these ROM's will contain Sense, some won't, that should be fairly clear before you flash them.
Sense isn't open source, so when 2.2 comes, the first unoffical 2.2 updates will only use stock Android. Its also quite resource heavy, so you'll find the fastest ROM's with the best claimed battery lives will generally do without it. (When I was running the Desire ROM on my Nexus I had >60MB less RAM than when I was running Cyanogen's ROM's)
Rooting WILL invalidate your warranty, and its not hard for HTC to tell - flashing back to the shipping ROM
WILL NOT undo the rooting process, although if you're lucky the kid in the store won't know what's going on and you might get away with it

. Loosing 12months warranty for the sake of Apps2SD and Wireless Tethering seems a little silly to me
Do plenty of research (XDA is the best place to start) and make up you own minds. If Vodafone
ever call me back and I ever get hold of a Desire, I won't be rooting it (Because I'll be selling it on the MM or ebay) but even if I wasn't selling it and was keeping it, I would almost certainly be waiting a couple of months before rooting - I fail to see the advantage yet.
Those looking to free up space for apps have a look in the mange apps menu and see what's taking up all the space. Google Earth and Sat Navs are the usual culprits
I feel like Steve Jobs after that essay

Hopefully its made some things clearer to some of you - There will be on person asking but 10 wondering no doubt
If it hasn't then tough

Try
XDA if you want a more in depth explanation
On that note: There is an interesting technical article on what causes the pink tints on XDA too,
here