The closer you get to popular neighborhoods, the more expensive.
Avoid the Tenderloin and Bayview/Hunter's Point. Yes, they have cheap rent. They also have high crime rates, drug usage, etc.
Some of the most inexpensive but nice areas to live are in the Sunset(near Ocean Beach along the N-Judah MUNI line) and Twin Peaks. The problem with Twin Peaks is that you get a great view and slightly lower rent, but there are no trains that go up there and limited MUNI bus lines. You're also not quite next to any popular places, so its not as easy as walking out your front door to go to the bar.
I live in Lower Haight near Haight St & Filmore. I'm paying about $1000 a month for my house that I'm sharing with one roommate. However, I only have this lucky situation because I've lived here for 3 years, and my old roommate for 2 years before that. So I've basically inherited a lower rent.
Craigslist is the primary place to find apartments in SF. Be aware of the occasional scam. If you see postings that are too good to be true, i.e. low rent for an otherwise awesome place, be wary. Typically when you reply to these, you will get an email a day or so later where the person is saying they are out of the country and that after you make the deposit, they will mail you the keys. No, no no no no. Stay away from these scammers.
One of your best bets would be for you and your roommate to find one or two other people that are either looking for people to fill vacancies in a house, or looking to get a big house together. There are many houses in SF that have 3-7 rooms, so often you can find inexpensive rooms like that.
You might also have luck with the last idea yourself. Given the number of people on HN that live in or around SF, you and your buddy might be able to hook up with some locals and rent a new house together, or might even find suitable vacancies in a geek-friendly house. =)
Here's the craigslist link you want to use http://sfbay.craigslist.org/sfc/apa