I've not rooted an SGSII, but the HTC isn't too bad.
XDA Devs or the CM site are where I'd start too in your shoes.
IIRC from doing my old Galaxy Portal, there are three stages:
Install 'insecure'/root access granting kernel (edit - Pugs is correct, it's actually the baseband you are modding - do a mental find/replace for the rest of this post, too lazy to DIY )
Install Recovery/Mod application
Use RecoveryMod application to format the onboard storage and write the new OS to the device.
Install an 'insecure' kernel
One that allows the user to perform root operations. Such as formatting the internal storage, etc. This is the complicated part that requires allowing USB debugging on the phone, having KIES (for driver support of Debug mode) installed, and using Odin to push the new kernel to the handset. That's a bit in depth, but once you get your head around what it's doing, it makes sense.
Once you have pushed the new kernel in, you can install a recovery mod program such as ClockworkMod, or similar. These are available from the Play Store. Use whichever one your guide of choice recommends. Often it's just the developers personal preference, sometimes there's a reason for it. Don't try to be clever....!
Download your modded image (Cyanogenmod etc) of choice and place it into the root of the SD card/storage or wherever the recovery app tells you it wants it.
Format C:, SETUP.EXE
You get a reboot menu called ClockworkMod recovery when you try to power off the phone - "Shutdown, reboot, reboot into Recovery" - which boots you into a separate, very minimal OS, which because you rooted it with the new kernel, has rights to wipe the storage and OS - which the 'secure' kernel does not let you.
You choose to install a ROM from a Zip, point it at your ROM of choice in your storage device on the phone, and it unpacks it, and writes it to the phone. It should then do something common sense like reboot into the new build. First time boots take a while - give it around 10 mins before giving up and starting again
Those are the basic concepts - the root, the recovery mod, and the OS install - there are minor details such as getting a program that allows you grant SuperUser rights (think UAC on windows - are you sure you wish to allow this app system level rights, etc) which sometimes come into play, again, depending on the guide you use. Certainly, after you have rooted it, any application that lets you, say, override the CPU governer from the factory default - so you can set the minimum and max CPU speed to below and above what the factory recommend for power efficiency - then it'll require SuperUser access. Without root access, you just can't do that.
The Samsungs have always been a touch trickier to root, but it's well worth doing it, especially as you point out, to get rid of the crapware that comes with operator subsidised phones.
Currently running a CM9 port for the HTC Saga (AKA Desire S) which is pretty much feature complete, runs perfectly well (very smooth most of the time, but lack of RAM makes it bog down a bit after a while due to background tasks) but it's stable as you like, and has 'hard crashed' perhaps twice in a year and a half....