Looking back, I'm wondering whether the absolute-cheapest Maplin's soldering iron might have been a major hindrance. Does anyone have any recommendations on good soldering irons? Currently I'm only planning on building a Gertboard and then looking for further inspiration, so it doesn't have to be very heavy duty, or able to heat large masses.
UK availability is necessary, cheapness is good (but not to the point that I'm likely to find it just too difficult and give up grumpily).
Learning a skill with poor quality tools results in poor quality learning. Many people prefer not to believe that, to their personal cost.
It depends what your budget is. Top of the shop would be Metcal or JBC, but way above your price point. Weller is your next best level. You do want temperature-controlled, but to begin with I don't think you need fine adjustment. A Weller will last you the rest of your life. I've heard good reports on Hakko and Xytronix soldering stations, but they may be more complex than you need.
I'd steer clear of Maplin and look at Rapid or Farnell. I'd look at:
Xytronix 169 station with a selection of bits (£74.57 + P&P + VAT from Rapid);
Oh, and yes to silicone cables, you really do need the flexibility when you're working on smaller stuff.
To make the experience easy for you, I'd also suggest getting a tip cleaner. If you have a dirty tip you will struggle with making good solder joints.
And start with leaded solder as its much much easier to use than lead-free (although there are some good ones now on the market, such as Multicore - just need a hotter tip and keep it clean).