A lot of good info, but as someone who lived in Minneapolis/St Paul for 7 years (4 as an UG), and loved it, I want to add some points:
- You can definitely find a studio for under $600, even a 1br. At that price, though, for a 1br, you will have to do some tradeoff between size, quality and neighborhood. I had a large 1br in an old, unrenovated (but historic and quite charming) apartment in a marginal neighborhood for $685. But when I left, it took the LL months to find a replacement, so it's possible I paid over-market value.
- A good neighborhood that hasn't been mentioned is Seward, which is south of the West Bank. This is a really cute neighborhood with a nice mix of students and families. It has a great co op, several supermarkets, a few coffee shops and some great restaurants. It's also right near the river, which is nice. The rents there are cheaper than Uptown. Oh, and it has a Light Rail stop, so it's convenient to get downtown or to the airport/mall of america.
- In general, you might want to avoid the neighborhoods north of Lake St, between Hiawatha and Nicollet*. These neighborhoods, Phillips and Whittier are some of the only high-crime neighborhoods in Mpls. Of course, it's Minneapolis, so the crime rates are still low, but there are definitely better neighborhoods to live in. These neighborhoods do have some good restaurants, though, so definitely check them out in the daytime.
- Minneapolis has some of the best food I've ever had, and I've lived in NYC, Seattle and Boston. Particularly good is the Vietnamese food. Mpls also has a huge, cheap farmer's market, which is great for that grad student budget.
- I like St Paul a lot, especially the Grand Ave area, but beware that the express buses from this neighborhood only run at rush hour. If you expect to socialize in Mpls or work late in the lab, you might want to live near University Ave - there's a bus that runs down University Ave straight to the U and it runs all night.
*Though close to Nicollet it's a lot safer, and Niollet has some of the best restaurants in the city (its nickname is Eat St).