unable to locate package mysqld-server

I just set up a fresh install of Ubuntu 12.04 on my VPS, and I cant for the life of me install or even locate MySQL server..

apt-cache search mysql 

gives no results on mysql-server/mysqld-server

apt-get install mysqld-server 

as well as many variations just gives the output in the title:

unable to locate package mysqld-server

I have added the universe repo, in which it should be located, but nothing. Google yields absolutely nothing on this, the only relevant info is just to run those commands, and to run another that is supposed to work:

apt-get install Lamp-server^ 

(may be misspelled a bit, but its close and I ran the correct one earlier) which also didn't work at all, it said the same thing, unable to locate package "etc"

Am I missing something here? should I have a specific repository I don't? should I be running a different command? or did ubuntu 12.04 drop mysql support or something?

Thanks for your time guys, hope I can get this to work, its driving me crazy.

You want to install mysql-server, which does exist in 12.04.

If you can't find it maybe you've done a clean install and haven't done an update yet, so do the following:

sudo apt-get update
sudo apt-get install mysql-server

If that doesn't work update your question with what happens.