Con phpmyadmin es super sencillo. Entras, y justo en la portada te sale "Crear nueva base de datos". Le pones un nombre y te la crea, así de simple. Otra posibilidad es que tengas un hosting contratado, en ese caso a veces ya te dan las bases de datos creadas