Ubuntu's definitely a great place to start. Check
HERE for a wealth of information on how to install/configure stuff.
As for the Gnome/KDE question...
Download Kubuntu as well - it's the KDE version of the original Ubuntu (which uses Gnome) - and see which one you like best!! I personally prefer Gnome.
I wouldn't worry about your old hardware - I have ubuntu running on a old Pentium MMX laptop (<= 333mhz?) with 64MB of RAM and can surf wirelessly anywhere in my house. I use XFCE4 (a 'light' window manager) instead of Gnome/KDE and it runs perfectly (this set up is known as Xubuntu).