Given they've just been given the story during planning (regardless of it being a new story or not having estimated it earlier) you have a few choices.
First, you can ask the product owner if the story can be left on the backlog so that it can be properly checked and estimated during this sprint, and take it next sprint.
If that's not possible, another option is to do it in a spike - a time-boxed story to investigate something or to try something out - and then you'll have a head start for doing it next sprint.
Finally, if you really must start on it this sprint, then try and find out as much as you can during planning, and take the story but make it clear of the risk that it may not be completed this sprint. If it doesn't get completed, so be it, you've done some of it and now know a lot more about it for the next sprint.
Remember, estimates are just the best estimates with the information you have at the time, and can be revised later when you have more info.
Also remember you should be spending about 5%-10% of the sprint in refining the backlog. Doing this really helps keep the planning meetings shorter, more focused and more productive.
Firstly, what happens with those user stories? Do you just carry them over into the next sprint?
It depends. If no other story has a higher priority, then, yes, they are moved into the next sprint. If other stories have a higher priority, then they might be moved back into the product backlog if there is not enough room in the sprint to accomodate them. This all happens in the sprint planning, based on the priorities assigned to each story by your Product Owner. Since one of the purposes of agile methods like Scrum is to maximize the delivered value while reducing the time, it all comes down to how much value is added by finishing those stories.
Regardless of what happens, you still need to strive for a potentially shippable product at the end of the sprint. This might mean rolling back to ensure that the end-of-sprint product passes all tests and the completed features are fully usable by the user without any significant problems.
If so, should they be re-estimated? In my view the work remaining on these user stories can be minimal or a lot? If not, why not?
I would not reestimate because, in Scrum, you estimate a story when you accept it, begin work, and don't have a concept of partially complete. A story is either 100% complete, tested, and accepted (done) or it's not done. If there's no concept of partially complete, there's no way for you to determine how much work is remaining on the story. It appears that I'm not alone in this thought, either. You estimated the work that you thought you can do, so leave this data point in and make it a point to discuss why the estimate was off in your sprint postmortem and try to avoid making that mistake for future sprints.
Best Answer
Certainly, you should be able to pull in whatever is at the top of the product backlog.
But be careful.
Make sure that pulling in the new story will not interfere with the delivery of the stories you have actually committed to. You really should make sure they are wrapped up and ready to go (deployed even). At the very least you need to make sure that the new probably-unfinished code does not get mixed up with the finished deliverable code.