caph:
I've got a standard 1602 LCD display which works fine but I cannot solder the pin headers on.
As others have noted, it does seem like you aren't getting the pin hot enough for the solder to wet the surface of the pin and "stick" properly. There could also be a problem (again, as others have noted) if the pin headers are tinned for non-leaded solder; trying to use leaded solder on such pins can be very difficult (or impossible, unless your iron gets hot enough for the non-leaded solder to melt, which has a higher melting temperature than leaded solder).
Something that might help would be knowing the specs of the header pins (if you know them); unfortunately, if you got this LCD as an unassembled "kit", it might be impossible to know or find out. Do the pins look tinned? If they are a dull silver color, they might be (better would be to look at them under a low-power microscope - tinned pins will look rougher than plated pins). If they are gold colored, then they aren't likely to be tinned.
So - back to getting enough heat: What I've found while soldering (these past 20+ years) is that if you tin the tip of your iron, then apply a tiny blob of solder to the iron, you can use that blob to heat things up faster. Press the blob (and tip of the iron too!) against the lead and the pad; when the temp of both is up properly, the blob will flow and stick to the pad and lead - at that point immediately add more solder (keep the solder near the tip while you wait - for small leads and such, with a hot iron, it should only take a couple of seconds to heat up max before you need to add the solder). When you have enough solder, move on to the next pin (whatever "next pin" means in your soldering situation). If you do this right, when you pull the iron away you'll still have a bit-o-blob attached, and you can somewhat rapidly jump from point to point soldering quickly.
If you stop - you might find the solder "oxidise" and burn out all the rosin (it stops smoking); at that point, clean your tip (a pure brass or copper "sponge" works best - in the "old days" we used a damp sponge, but this is frowned on now because it cools the iron down - meaning it needs to get back up to temp first before continuing using it - and it degrades the tip); never use sandpaper if you can avoid it; sometimes you might need to - in that case, immediately tin the tip and keep it tinned. While it is true that soldering irons do have a "special coating" (nickle over copper or something like that), and stripping it will cause the tip to degrade quicker, it isn't like it's going to fall apart immediately. Tips are cheap, too (unless it's an integrated cartridge heater and tip - those are pricey). And never use a soldering iron for anything but soldering, like "cutting" plastic or such - if you do, dedicate that soldering iron to that purpose, and don't use it for anything else).
Finally - regarding temperature controlled irons: I like them - they heat up quickly, maintain a constant set temperature - but they aren't absolutely needed for proper soldering. I learned on an el-cheapo 30 watt worse-than-radio-shack iron; I still have that iron. The tip looks like hell from it's constant use and abuse. It's probably been sanded and/or filed once or twice. I keep the tip tinned, though, and it still works great. The key is proper tinning, keeping that small blob on the end, and quick/deft handling of the soldering iron to do that "point-to-point" solder jumping. Because it runs hotter than smaller irons, it maintains that heat well, but on small parts this can be a problem - you might apply too much heat to the joint. Just move quicker - that's your temperature control.
I really think I need to make a video of myself using it to solder on a PCB, just to show that it isn't the tool (though they are, again, nice to have and use) - but the person using it, and their application and practice of the skills.
