Radioshack has magnet wire
Yeah, you're going to want magnet wire, fairly small gauge, too (36+ gauge). Your also going to want a method to wind it; ideally you would use a lathe, but if you don't have one handy, a variable speed drill can work, provided you can somehow lock the button in place to continuously power it. If you can rig a footswitch (like for a sewing machine) to control it, all the more better.
Radio Shack isn't the best place to get magnet wire, though, at least for the amount you will need. Check out some surplus dealers (All Electronics might have some); you could also (possibly - might be difficult) take apart a transformer or electric motor and use the magnet wire from the coils.
If you want to know how to really wind them, look on Google Books for articles dealing with homemade electric motors and such; if you can find a copy of Alfred Morgan's "The Boy Electrician" - even better (note: this book is considered antique, and sometimes "rare" or "near rare" depending on the dealer; you might spend a lot of money on a copy unless you get lucky - but it is an awesome "turn of the century" - that's 19th to 20th century, BTW - book detailing how kids - mainly boys - used to play with electrical gadgets, back when Thomas Edison and Nicola Tesla were still alive and hale).
A good place to find a reprint of the book (cheaper, but not as cool to own, IMHO), as well as other books that may help you, can be found here:
http://www.lindsaybks.com/
Lindsay Books is an awesome "turn-of-the-century" book reprinter; they have everything you would need to know how to go from an agrarian-based way-of-life to an early 20th century industrial machine shop (that includes how to build a furnace to melt the metal to cast your own fittings for machines!).
The basic idea, though (if I remember my reading correctly) is to take an iron carriage bolt (steel will do, but iron is best), and give it a coat of shellac or laqcuer (or some other non-conductive coating), then wrap the shaft of the bolt with paper (or other insulating material), and place two fiber (carboard or other) washers at each end, then shellac it some more. Then, you chuck the end of the bolt (where the threads are) into a lathe (or drill) chuck, and take a length of the wire and place it around the end near the head, pass it through a hole or something, and leave a small bit dangling, then secure it so that it doesn't wrap around anything or get caught. Then you slowly start the lathe up, and feed it wire until you have a layer built up; you do this carefully, keep the wire neat and wraps side-by-side and tight. when you get to the other end (next to the other fiber washer), you keep things tight, shellac it, let it dry, then start the next wrap (you probably want to keep track of turns and number of layers, too), shellacing each when you get to the end, before you start back. When you have all the layers you want, you are done; you can then give a final shellac coating, test the continuity, etc (you might want to do this on each layer, though).
It isn't an easy process, but if people did it in the 19th century, you can do it today (it might be interesting, though, to attempt to build an Arduino-controlled electromagnet winding robot!). You might want to substitute in modern materials (keep the iron bolt if you can find it, but there are better options for shellac'ing and paper insulation/washers - silicone, acrylic, etc).
Good luck!

[edit]Titles from Lindsay that are likely applicable:
http://www.lindsaybks.com/bks11/xfmr/index.html
http://www.lindsaybks.com/bks/boyelec/index.html
http://www.lindsaybks.com/bks8/magn/index.html
http://www.lindsaybks.com/bks2/elmag/index.html
http://www.lindsaybks.com/dgjp/djgbk/coil/index.html
http://www.lindsaybks.com/bks4/solen/index.html
http://www.lindsaybks.com/bks5/dynamo/index.html
http://www.lindsaybks.com/bks/lejay/index.html
I look at that catalog, and I realize that despite us moving forward, it seems we have also "lost" a lot of knowledge; at least, these things are taught much or shown much in school, but they are still applicable in today's world.[/edit]