Para crear una base de datos nueva puedes hacerlo de, al menos, dos formas. Abre un Terminal y ejecuta lo siguiente.
$ mysql -h servidor -u usuario -p
Enter password:
mysql> CREATE DATABASE nombre_de_la_base_de_datos;
quit
También puedes usar la orden mysqladmin.
$ mysqladmin -h servidor -u usuario -p create nombre_de_la_base_de_datos