First things first being that when you insert into the database, you should either use mysqli and it's prepared statement or use [man]mysql_real_escape_string[/man] to help prevent SQL injection attacks.
To see if a username is taken you can do it one of two ways. You can either alter your database to have a unique key on the username column which will result in a failed query when you try to insert a duplicate username; or, you can do a quick SELECT query (similar to the INSERT query you already wrote) which just looks for "WHERE username = '{$username}'".
One example would be:
<?php
$con = mysql_connect("localhost","******","******");
mysql_select_db("Inregistrare", $con);
$isUniqueQuery = "SELECT Username FROM inregistrare WHERE username = '%s'";
$query = sprintf($isUniqueQuery, mysql_real_escape_string($_POST['Username']));
$result = mysql_query($query);
if (mysql_num_rows($result) > 0)
{
echo "That username is already taken.";
}
else
{
$insertQuery = "INSERT INTO inregistrare (Nume, Prenume, Localitate, Varsta, Sex, Username, Parola) " .
"VALUES ('%s','%s','%s','%s','%s','%s','%s')";
$query = sprintf(
$insertQuery,
mysql_real_escape_string($_POST[nume]),
mysql_real_escape_string($_POST[prenume]),
mysql_real_escape_string($_POST[localitate]),
mysql_real_escape_string($_POST[varsta]),
mysql_real_escape_string($_POST[sex]),
mysql_real_escape_string($_POST[username]),
mysql_real_escape_string($_POST[parola])
);
$result = mysql_query($query);
if (mysql_affected_rows($con) == 1)
{
echo "Felicitari! Ati fost inregistrat! Asteptati 5 secunde sau apasati <a href='conectare.html'>aici</a> pentru a va putea loga.";
}
else
{
echo "Unable to save registration.";
}
}
Hope that helps.