After setting the proxy in "fink configure", it still did not work in Leopard. Running "env" showed that the http_proxy & friends were indeed set. Eventually I did "sudo -s", then "env", thus noticing that those variables apparently did not carry over to sudo.
Apparently sudo has some sort of whitelist in /etc/sudoers, to which I added the proxy variables. With that, fink worked.