Overview

For a good overview of permissions and the security model, see "Who Sees What" https://www.youtube.com/playlist?feature=iv&list=PL6747B4DAE356E17C&src_vid=j95gONjVNFU&annotation_id=annotation_3209566513

Basically - permissions is the fields that a user can see and the things they can do in Salesforce (eg Export Reports), these are controlled by Profiles and Permission Sets. Sharing Rules and Roles controls which records users can see. Think of sharing rules as slicing your data horizontally, (which rows in a spreadsheet) and permissions as dicing your data vertically (which columns in your spreadsheet).

Setting up Permissions and Users for a new Org

You start off with an Admin user only... you need to get your whole permissions structure set up.

Steps:

Ask Salesforce to enable the setting for admins to login as any users http://help.salesforce.com/apex/HTViewSolution?id=000089838&language=en_US
Decide on your groups of users, their hierarchy and what data they should see.
Clone existing profiles - only do as few as needed - focus on the tab and app permissions and basic object permissions. Specific object and field permissions can be done via Permission Sets.
Set up the Role Hierarchy
Set up Organizational Wide Defaults - usually Private on the main objects such as Accounts, Leads etc unless everyone in the org should see and edit everything.
Create Sharing Settings
Create the Users
Test Test Test

Annoyances

Why oh why does a new developer org need 35 profiles? Why does a new developer have custom profiles? (at least I can delete them).

Dicing

Field Level Security

https://help.salesforce.com/HTViewHelpDoc?id=admin_fls.htm

Permission Sets

See the Salesforce Help for Permission sets as to what can be done in Permission Sets and what can be done in Profiles.

Slicing

Roles

Roles control which records users have access to. Eg West sales reps should not see East sales reps's leads, but the Manger should see all of them etc.

Sharing Settings

Eg ensure that the Managers of sales reps can Read and Edit the Leads, Accounts, Contacts, Opportunities, Cases of their Subordinates.

See https://help.salesforce.com/HTViewSolution?id=000001139 for security for each edition of Salesforce.