I used bolt cutters to cut a piece from one of those wire campaign poster sign legs, took that piece and wrapped it (all in the same direction) with wire that was unwrapped from a small fan motor, then hooked it up to a 9 volt battery. I chose that as the iron core because I read that bolts are hardened iron and aren't as good as "soft iron". I verified that magnets stick to it. The result is nothing, not even the slightest capability to move a paperclip (that does stick to magnets). Lick test tells me the battery is live. I'm sure the wire is coated because it was visible when I was burning the coating off the loose ends (and because of where I got it.) I know the circuit is complete because hooking a little bulb with it in series makes it light up.
My suspicions:
1) The iron wire core I chose isn't suitable despite sticking to magnets readily.
2) The iron is too big/small to be affected by the too big/small copper wire wrapped too few times with a too weak power source. (But it should show at least a little magnetism, right?)
3) The wire shorts in such a way that it bypasses the part where it makes an electromagnet.
4) I've forgotten some fundamental detail about how this works.
Pictures below. How can I determine what went wrong and/or how can I make sure it works on my next attempt?
Left to right: Where I got the wire, the electromagnet I tried to make, another segment of wire, and the Lego brick its intended to fit in 
A close up. The plastic pieces on the ends are just to hold it inside the brick. Its put together with super glue.
Best Answer
Just from a visual inspection of your photos, I think that some of the comments that you have received have sort of identified your problem. This answer is just to add some more detail.
Your coil doesn't have enough turns of wire to generate much of a magnetic field. In addition to that, the DC resistance of that wire is very low. When you connect the coil to a 9V battery, the internal resistance of the battery is very high compared to the resistance of your coil. This results in most of the energy being wasted inside the battery as heat.
One of the comments suggested using either an alkaline "D" cell or a "AA" NiMh cell. Either would work much better than the 9V battery because the internal resistance of those cells is much, much lower than the 9V battery.
Just as a suggestion: if the winding on the fan where you are getting your wire from is still mostly intact, why not try connecting a "D" cell to the wires coming from the coil and seeing what happens? There are many turns of wire on that coil and you know that the core is soft iron (or equivalent) - this would work nicely as an electromagnet.
If you want to make your electromagnet work better, you will need to rewind the coil with many more turns of much smaller wire.