You need the board with copper strips joining the holes in one direction, I think the board you linked only has pads, with no strips. I can't really tell from the website which boards are suitable - the pictures are small and the descriptions aren't terribly helpful. The board I have here is from Farnell, but is quite old and the code is no longer recognised by their website. I'll have a look tomorrow in the paper catalogue to find the right one.
A soldering station (temperature controlled iron) is indeed very useful, but probably not really worth it to begin with. If you are buying an iron I've found the Antex type 'C' 15W or 'XS' 25W are both good, although I prefer the 15W one for small jobs as the 25W is a bit large, but the 15W isn't really up to it for big joints. If possibly get the version with silicone cable - partly as it is heat resistant, but also as it is much more flexible, making handling much easier.
Also get a proper stand. I must admit to having a soldering station at work and much preferring it. I also find a small vice and some 0.2kg weights very useful for holding items whilst soldering them, certainly much better than a 'helping hands'.
See the beginners guide on this website for a quick guide to soldering. EPE magazine have (or certainly used to have) a comprehensive soldering guide on their website at www.epemag.co.uk