New to agile and I'm not sure how to start.
After reading your post I think you're misunderstanding it and you should start with reading what agile really means and tries to accomplish.
The idea is to create small parts of the project in sprints.
Close, but not close enough. The idea is to deliver working software at the end of each sprint (one part of the system can fit into one sprint, or not). The database can be seen as working software if and only if the database is what you deliver to the customer.
However the project I'm working of requires a database and the database must be almost functional to do anything with the project.
Why does it have to be almost functional? Does every feature of the system use the entire or most of the content of the database? Because if it doesn't, there's no point in designing the whole database beforehand.
So how do Agile projects handle this, do you start by creating the database?
Agile doesn't handle database or system design. It tells you how to manage your project. With that in mind, you start by identifying all the features of the system and put them in the product backlog. Then you, along with the product owner, assign priorities to the features in the backlog. After you've done that you start taking features from the backlog and create sprints (usually 2 to 4 weeks long). When a sprint is over you should have a new working feature in the system that can be delivered to the customer.
How would you do so, for example if using Scrum how would you do the user stories and test the db.
I might be wrong, but there's no point in testing the database. You can test the code that updates the database. Of course, you can test your programmable part of the database but that can be achieved by testing the code that calls it.
Would you rather do parts of the db in a story that also requires code.
Agile is by no means a silver bullet to project management and can spell disaster when not applied correctly. Try to spend some time reading about it (you can find plenty of resources here or on stackoverflow), maybe find someone that has already done agile and can help you to get up to speed.