When you use stories - or you may call them tasks or something similar - you can use a story as the unit which needs to get estimated. Initially it will be hard on the team. For example how would you estimate the size of a story if the estimators have different roles such as developer, business analyst, tester, user interface expert, performance engineer, etc. How can a developer assess what amount of effort is required by the user interface expert or the tester?
In reality they don't need to. With the initial set of stories all you need to do is agreeing on some relative sizing. These sizing will be in all likelihood completely off anyways. That fact of life should make this first step more relaxed. After the iteration is complete you look at how much you completed. Let's say you use NUTS as the unit for relative size. (NUTS = nebulous units of time, credits go to Darren Rowley from whom I learned this one.) Then you can look at the completed stories at the end of the iteration and see whether the initial estimate was correct. Was story 'xyz' really twice the size of story 'abc'? It doesn't have to be scientifically perfect. All that matters is that you give it your best shot and record the actuals.
By recording the initial estimates and the actuals you are already on your way to improving your estimates. Please keep in mind that generally estimates are provided by a cross-functional team rather than by individuals. And ideally the estimates are provided by the team that will do the work eventually.
By default you should sign up for stories that don't fit an iteration. If they are too large, break them into smaller pieces. At times, however, it can happen that a story is not complete at the end of the iteration and at the beginning of the next. One example could be that some capacity was left over towards the end of the iteration and work on an additional story was started.
If a story is incomplete at the end of the iteration (for whatever reason!) then the team should assess whether the size of the story is still good or whether it needs to be updated (either way!). If the estimate is changed then you should record the updated estimate as well. Why? The only reason to record the updated estimate is to allow for a proper capacity planning in the new iteration. You need to know the updated/current estimate and how much is left, so that the team doesn't over-commit but signs up to only as much work as they think they can accomplish.
So in effect, you are recording three numbers: The initial estimate, the updated estimate (history of this is not required), and the actual figure once the story is complete. The comparison of initial estimate and actual number allows you to measure how - as a team - you become better at estimating. The updated estimate is important for understanding how much work your team signed up for in a particular iteration.
If you like you can use a simple spreadsheet for recording these numbers. Make sure you add some dates for further analysis, e.g. how was the quality of estimates in quarter one compared to quarter two? A team is getting good at estimates if you use a mix of about 10 to 20 stories and the delta between the total of initial estimates and the total of actuals is less then 10%. I have worked with teams that got this figure to less than 5%, which is excellent. Always keep in mind that we are talking about estimates - we are trying to look into the future - and not about prediction.
A word of caution: Recording these numbers is important as a tool for the team. Stay away from the temptation of using it to measure the individual performance of a team member. Even if unintentional, as soon as any team member even just perceives it as a performance control mechanism, tracking the estimates and actuals is dead. The team must be able to update estimates without fear whether the fear is induced deliberately or accidentally.
Working with this tool - recording the estimates and actuals - and experimenting with it can lead to an extremely powerful tool. It doesn't increase the capacity of the team but it definitely will lead to much improved estimates and to better predictability of the deliverables of the team. And that in turn will lead to higher customer satisfaction. The spreadsheet I mentioned should not drive the team meeting. Instead it should just reflect the outcome for future reference. The team builds their body of completed stories that can serve as reference points for new stories for which a relative size is required.
Therefore: Experiment with this tool until it works for you. If it doesn't feel right chances are it is not working yet! Be courageous, try something, don't be disappointed if it doesn't work, try something else, then improve.
Good luck and have fun!