How do new team go about estimating user stories

Do they have a Definition of Done which asserts the level of quality needed for work to be released this Sprint?

They do have a DOD drafted, however not comprehensive. This is work in progress

Each story has a certain acceptance criteria agreed between PO and the team.

A good Definition of Done is always a work in progress. That doesn't stop a Scrum Team from needing one, now, because work is planned for release this Sprint.

Knowing the level of quality needed for work to be released is instrumental when forecasting how much of it can be taken on.

I'd highlight one statement from the Scrum Guide in particular:

Product Backlog items that can be "Done" by the Development Team within one Sprint are deemed "Ready" for selection in a Sprint Planning.

There is no specific description of what an estimate is. The only guidance regarding the estimation of Product Backlog Items is that a refined Product Backlog Item that is ready for a Sprint can be completed in one Sprint. What that means is up to the team, their way of working, and their Definition of Done. Having a clear Definition of Done and an understanding of how they work (especially with respect to collaborative development and peer reviews) can help the team. No other level of estimation is required, although some teams do find it helpful to estimate in different ways.

I'm going to the heart of agile software development for my answer.  Empirisicm is about making a decision based upon what you know now and then doing something.  As you learn more or gain new information, inspect what you have and adapt.

So this is a new problem space. That just means the team needs to learn more about it.  How do software developers learn?  All of the ones I know will say that they will need to work in the space or experiment with the technology in order to learn.  So suggest to the team that they do something based on what they know and help them understand that as they learn, it will become easier for them to make estimates. 

I had this situation happen to 4 Scrum teams for which I was the Scrum Master.  All 4 of them happened at exactly the same time.  The company was moving away from a complete Ruby on Rails situation by decoupling the User Interface as a Java application.  The teams had basic knowledge of Java but didn't feel like they were fully versed in it.  So, I suggested to them that each team take 2 basic workflows for their frontend and work on implementing them. I made it clear that the expectation of a potentially releasable increment was still there but emphasized the word "potentially".  All of the Scrum Teams agreed that no one really expected a great deal of finished, polished code to be created and that they would be focused more on learning than on the final product. They did no estimates at all for the first 2 Sprints.  They just took workflows, broke the work into small units of functionality and started working.  All they did was focus on work, paired heavily, learned how to write Java code and how to make Java communicate with Ruby on Rails.  After 4 Sprints, all 4 teams felt more comfortable with estimating efforts and felt that they had an understanding of how much work they could actually accomplish during a Sprint. By the way, the first Sprint was a disaster for all 4 teams. None of them had anything that would be worth releasing to Production. But everyone agreed that they learned a lot from the efforts and that it was the best thing for them to do. 

Remember that Scrum is a framework not a process.  Empiricism is about learning from what is available.  Failure only occurs when you do not learn from what you are doing or what occurs as a result of something that is done. Every Sprint can be a success if you agree on a definition of success for that Sprint.  

New project and a new team, they have not worked on anything similar to this project in the past.

They have picked (rather asked by the PO) up few stories in the sprint planning that are of high priority and bit complex. As they have not worked anything similar in the past they are not able to use the relative estimation.

A lot of Scrum Teams start on a blank sheet. But nevertheless, they will need to estimate somehow.

You say they cannot use relative estimation, well, they cannot for the first, but for the second they can relate to the first.

So the only challenge is to estimate one story that will work as the reference story for all other stories to come. There are several ways to do that, you could go through to find the smallest and give that two points, as there might be smaller to come, or you could go for a medium one to give that a 5 (or 8) points and use that as first reference.

The very first estimate will take longest, but once you have a reference, the others will be much easier to estimate.