Get your hands on a copy of the Prague In Your Pocket guide, they have links to rental agencies which can get you started. Consider booking something like a small apartment for a week or so, to give you time to find something more suitable once you get there and can do some looking on your own. Personally, I'd opt for a place mentioned in the accommodations section, rather than the real estate section, because they don't charge as much, and you can usually get a discount if you stay more than a few days. B&Bs are also a good bet for this kind of longish, short term accommodations.
When you get into town, hook up with expat community groups when you first arrive (check out any and all groups you can - reading rooms, cultural groups, whatever - In Your Pocket will have contact info) and see what you can find by talking to people who've lived in Prague for a while. If you go through a rental agency, you'll pay a lot more, but probably find an awesome place...if you go through the local network you'll get something a lot cheaper, but it might be in a Soviet era block house. Trade offs at every hand.
We got a fabulous flat in a circa 1850s building in the Old Town of Vilnius at about a third the cost if we'd have gone through an agency, by taking the local approach - a friend of a friend of a friend kind of thing. Or you may find someone who's looking for a roommate, which can also be a great option if you want to live in pricey central Prague.