SIM cards are pretty cheap in Brazil. Pre-paid phone packages are usually more expensive than in other countries, so I recommend you get your phone unlocked and bring it with you. Register it with customs and avoid own-brand operator shops ("Oi", "TIM Shop" etc.).
One you get through all these obstacles, you'll find out that your new Oi Chip (Oi SIM card's commercial name) comes with R$10 in credits, which is good for a few minutes' conversation (actual talk times will depend on the region you're in, Oi has different prices for each State covered).

All the hassle you'll probably have to go through to get your SIM, made all the more painful by the fact that shop attendants don't usually speak English or any foreign language (you'll be lucky to find one who can speak Portuguese properly). One could argue that this is due to the government-mandated ID verification, but I think blame lay with the terrible training and complete lack of vision by phone companies' management.

Couldn't they imagine that people without CPF would still need pre-paid SIMs?

You start with a single-rate option ("Oi Qualquer Hora") but that tariff can be changed to one with reduced prices during certain periods (morning 8a.m.-12p.m. afternoon 12-4p.m. night 4-8p.m. and "super night" 8p.m.-12a.m.).

From midnight to 8 a.m. all plans have reduced call charges.

Oi's main advantage is that it has by far the best GSM coverage in its 16-State area. CSD wap is available throughout, but GPRS is only available in State capitals and important areas (for tourism, industry, other major population centers, town with important universities etc.).

Without any top-ups your number (and SIM) will be valid for 180 days before it expires completely, in which case you'll have to cough up another R$31 for a new SIM and associated number. Credit validity as follows: 30 days for R$10 and R$15 vouchers, 60 days for R$25 vouchers (and R$20 top-ups purchased by direct bank debit if you happen to have a Brazilian bank account), 90 days for R$50 and R$100 vouchers.

Call and text message pricing depends on the State your number's registered in, and if you roam on Oi's own network throughout Oi's 16-State coverage area you'll pay local charges for your local calls and long-distance if you're calling your "home" area.

When placing long-distance and international calls, you have to choose your long distance provider every time. This is done by dialing a two-digit code. Code 31 (Telemar, Oi's parent company) gives discounts to Oi users. To place a long-distance call within Brazil:

0 + XX (long-distance provider code) + YY (area code) + phone number

For international calls it's the same thing except you start with two zeros (00) instead of one.

Services available are SMS, caller ID, voice mail (you'll need to call the voice mail number and set a password for this but the menus are in Portuguese), CSD, GPRS (in select areas), conference call, call waiting, SMS chat, news, and automatic domestic roaming.

Many of these services can be accessed by SATK (Sim Tool Kit), your own "Oi Menu". The booklet'll tell you of the options available. You can top-up your phone through this menu, among other things.

Another good thing about Oi's pre-paid service is that it informs you by text message of your credits and how much you have spent after every call. Nice.

It can be a pain to contact Oi's customer service number and talk to an actual person rather than a recording if you're on prepaid.

One thing to take into account with Oi, as well as most other services in Brazil, is that nobody speaks English. Don't count on that. In fact, sometimes I think they don't even speak Portuguese, or are unable to understand it beyond some standard, grammatically incorrect sentences. Customer care is abysmal and the telecoms authority isn't really regulating these companies, so it's no use to call them if you find any difficulties.

Also, MMS and POP e-mail is not available to pre-paid Oi customers. But you can send SMS to an e-mail address

Avoid Oi's own shops. Oi's selling phones like hotcakes right now so they couldn't care less about a customer without Brazilian papers or a dissatisfied customer.

Try and top your phone up from a bank account. If you use direct debit there's a R$20 voucher option and it carries a R$5 bonus.

CSD/GPRS settings for Oi and TIM Brasil phones can be found on this thread which I posted earlier this year

Oi's OK as a pre-paid option, nothing more. Prices are in line with the concurrence (they all raise prices at the same time while the competition authority pretends to look the other way).

Since you'll be here for a limited time only, their sub-par customer care probably won't bother you that much.

Signal quality, strength and availability put TIM to shame. All in all, the best pre-paid option in Brazil if you go the GSM route and happen to spend most of your time here in Oi's coverage area, which encompasses the best beach resorts and tourist spots anyway