The hard drive upgrade is not for the faint of heart, but it's not too difficult either. I put a new 120gb drive in my iBook G4 over a year ago. Make sure you have the right tools and use a good guide. I used this one from
iFixit.
The best piece of advice I can give about the install is get a bunch of blank copy or printer pages and step by step sketch out what you are doing and tape the actual screws you remove onto the sketch as you take them out. Then when you go to put it back together just go in reverse order putting the screws back in place. This way they don't roll away or worse yet you get them confused.
As far as your OS install, well that depends on what you want to do. If you have an external case with firewire then you can use Carbon Copy Cloner to create an exact copy of your current HD onto the new one by putting it into the external. Then all you have to do is switch out the drives and the machine will boot up just like your old one. I just did this with an iMac upgrade. It's by far the simple solution if you want to keep the status quo. And
Carbon Copy Cloner is a free program, nice! If you don't have an external for a 2.5" drive with firewire then I would suggest buying one anyway so you can put the old drive in it after you switch.
However, if you want to make a clean start then you will have to install a new OS on the blank drive with an Apple OS install disk. The install disk will give you access to disk utility to format the drive however you want prior to install.
If you need any help just let me know and I'll be happy to do what I can.
Edit: The drive you linked in the post above will not work. Your iBook takes an IDE PATA drive not an SATA drive. You want something like this
here.