Como fazer a função date() formatar uma data em português?

Use strftime() para criar a data por extenso, pois essa função pega automaticamente o locale. Como citado pelo @bfavaretto, basta informar o locale.
strftime() nas palavras do manual:

Formata uma hora/data local de acordo com o configuração de locale. Nome do mês e dia da semana e outras strings dependem do atual local definido com setlocale().

setlocale(LC_ALL, 'pt_BR', 'pt_BR.utf-8', 'pt_BR.utf-8', 'portuguese');
date_default_timezone_set('America/Sao_Paulo');
echo strftime('%A, %d de %B de %Y', strtotime('today'));

saida:

quinta-feira, 06 de março de 2014

%A: dia da semana por extenso.
%d: dia do mês representado com dois digitos.
%B: mês por extenso.
%Y: ano representado com quatro digitos.
Exemplo – strftime


Abordagem com IntlDateFormatter
É possivel também obter o mesmo resultado com as classes DateTime e IntlDateFormatter.
Os formatos de data e hora são:

Data
Constante  |Saida
FULL       |segunda-feira, 1 de setembro de 2014
TRADITIONAL|segunda-feira, 1 de setembro de 2014
LONG       |1 de setembro de 2014
MEDIUM     |01/09/2014
SHORT      |01/09/14
NONE       |
Hora
Constante  |Saida
FULL       |03h00min00s GMT+00:00
TRADITIONAL|03h00min00s GMT+00:00
LONG       |03h00min00s GMT+00:00
MEDIUM     |03:00:00
SHORT      |03:00
NONE       |

Exemplo – formato data/hora
No construtor é necessario informar quatro argumentos: locale, formato da data, formato da hora e o tipo de calendario

<?php
date_default_timezone_set('America/Sao_Paulo');
$data = new DateTime();
$formatter = new IntlDateFormatter('pt_BR',
                                    IntlDateFormatter::FULL,
                                    IntlDateFormatter::NONE,
                                    IntlDateFormatter::GREGORIAN);
echo $formatter->format($data);