In Unix, most programs rely on a MTA (message transfer agent) to do mail transmission. When a program wants to send a message, it executes
/usr/sbin/sendmail and gives it the entire message in stdin.
The Sendmail MTA was the first one to work this way (and still does), and other MTAs follow the same convention of providing a
[In this answer, Sendmail is the original MTA, and
sendmail (lowercase) is
/usr/sbin/sendmail (which comes with all MTAs currently used).]
mail() follows the Unix tradition and just passes the message to the
sendmail executable. Which means you need a MTA. You already installed Postfix, which is good. However, it does have a
sendmail binary, so if you don't have it in
/usr/sbin/, then you must have installed it elsewhere -- perhaps
/usr/local/sbin/ if compiled from source?
Reinstalling Postfix may fix the problem. If it doesn't, please update your question with details such as how did you install Postfix in the first place.
sendmail is somewhere else than
/usr/sbin/, then you will have to edit PHP's configuration --
php.ini. It's usually in
/etc/php5/, and Debian has three of those. (
cgi/ is for generic CGI/FCGI,
apache2/ is for the Apache PHP module,
cli/ is for when PHP is used from command line.)