Перенаправление и кодировка

$fio = $_POST['fio'];
$email = $_POST['email'];
$phone = $_POST['phone'];
$fio = htmlspecialchars($fio);
$email = htmlspecialchars($email);
$phone = htmlspecialchars($phone);
$fio = urldecode($fio);
$email = urldecode($email);
$phone = urldecode($phone);
$fio = trim($fio);
$email = trim($email);
$phone = trim($phone);
if (mail("...@m....ru", "Заявка с сайта", "ФИО:".$fio. ". E-mail: ".$email. ".phone: ".$phone , "From: ....@.....ru \r\n"))
 {     echo "сообщение успешно отправлено";
} else {
    echo "при отправке сообщения возникли ошибки";
}
header("Location: http://www.......ru/");
exit;

1) Вообще я бы на вашем месте смотрел в сторону PHPMailer, он более вменяемый и гибкий. Что-то вроде этого почитать (первая ссылка из гугла).

Если оставаться в рамках базовой функции mail(), то надо поиграться с заголовками и комбинацией utf-8 и base64.

Должно быть что-то вроде этого:

$fio = filter_var(trim($_POST['fio']), FILTER_SANITIZE_STRING);
$email = filter_var(trim($_POST['email']), FILTER_SANITIZE_STRING);
$phone = filter_var(trim($_POST['phone']), FILTER_SANITIZE_STRING);
$from = 'email отправителя';
$recipient = 'email получателя';
$subject = 'Заявка с сайта';
$message = "ФИО: {$fio} \r\n";
$message .= "E-mail: {$email} \r\n";
$message .= "Телефон: {$phone} \r\n";
$headers = "Content-Type: text/plain; charset=utf-8\r\n";
$headers .= "Content-Transfer-Encoding: base64\r\n";
$headers .= "From: {$from} \r\n";
$message = base64_encode($message);
$subject = '=?UTF-8?B?' . base64_encode($subject) . '?=';
mail($recipient, $subject, $message, $headers);
header("Location: http://www.......ru/");
exit;

Ответ по второму вопросу: header() не работает, потому что у вас имеется вывод текста перед отправкой заголовка. Здесь:

if (mail("...@m....ru", "Заявка с сайта", "ФИО:".$fio. ". E-mail: ".$email. ".phone: ".$phone , "From: ....@.....ru \r\n"))
 {     echo "сообщение успешно отправлено";
} else {
    echo "при отправке сообщения возникли ошибки";
}

Вот здесь подробнее.

1) Не совпадает кодировка сайта и письма, проблема и решение описаны здесь: http://www.cyberforum.ru/php-beginners/thread1642065.html#edit86406772

2) Нельзя делать какой-либо вывод на страницу перед выполнением функции header(). Если нужен и текст и редирект - можно попробовать сделать редирект через JS.