craiglist is probably a good place to start, although with housing, it doesn't make much sense to start hunting more than 30 days before you plan to relocate.
FYI, i was able to find a dog-friendly studio downtown for $795 a month in november 2010, so there are some pretty affordable options, especially if you look farther inland (i'm walking distance to the beach). if you don't have pets, that significantly widens your options too.