To outfit Catherine's mobile phone on our trip to Portugal (she was using my old T610), we purchased an UZO SIM (see What is a SIM card) from the local post office in Leça da Palmeira (I purchased an Optimus SIM for use on the same trip; we like variety!)
The UZO service appears to be a special pay-as-you-go brand of the TMN mobile provider; they have shops located all over the place, and may also sell the UZO packages, but I'm not sure.
The package -- about the size of a CD case -- was located on a rack near the postal wickets and cost 20 EUR and included a SIM and 20 EUR of calling time. On a card inside the package was printed the SIM's telephone number, a PIN code (entered when the phone gets powered up), a PUK code (entered if you forget the PIN) and a password for the UZO website.
To activate service, you simply insert the SIM in the phone, enter the PIN code, and you're good to go.
The UZO website is quite useful, and once you enter your telephone number and the password printed on the card that came with your SIM, you can check your balance, get a list of calls you've made, activate voicemail, sign up for optional features, and learn more about service. The website is in Portuguese only, but is well laid out and easy to make your way through even if you don't read the language.
You also get a short message on your phone after each call displaying remaining balance.
Topping Up Account
As Catherine never exhausted her 20 EUR balance, we never got a chance to explore the options available for "top up." I expect the post office would be of use here.