Summary: As EU citizen, you don't need to worry about getting a permit or facing serious consequences like detention or removal but you might indeed have to complete some formalities. If you don't, you risk a fine (on the order of €500 in the countries I know). Depending on the country, you have between a few days and a few months to do this but you never have to do anything in advance and can certainly just rent a place and start from there.
Many countries in the EU have a generic population register. Citizens have to report any change of address to the authorities (usually within a week or so) and if you move there with the intent to reside in the country for more than three months, you do too. On top of that, EU countries might require EU citizens to get some sort of specific ‘registration certificate’. In that case, you will often be asked to prove that you qualify for residence (i.e. have a job or have health insurance and enough resources).
In both cases, the penalty for failing to complete these formalities in time should be “proportionate and non-discriminatory”, which means no ban or no detention but at most a fine that should not be higher than what locals could face if they failed to register or to hold an ID (that's also mandatory in some countries). If you do qualify for residence under EU law (e.g. you have sufficient financial means), you cannot be asked to leave merely because you failed to register.
To find out about the exact rules in a given country, the EU Commission has a useful website providing specific country-by-country information but its quality varies depending on the submission by each member state.
For Sweden, you do not need to register in any way to reside for a few months but you need to register in the population register and get a tax number if you are staying longer than a year.
Norway isn't in the EU and hasn't provided any information to the commission but it is bound by association agreements with the EU and therefore grants broadly similar rights to EU citizens. Apparently, there is a form of mandatory registration there. More info on lifeinnorway.net