ANSI Common Lisp is (IMHO) and excellent book. It gets a little dense towards the end with macros and such, especially if you are just reading it, and not writing and experimenting with LISP along with it. But the first half is an excellent introduction (and I must stress introduction) to the basics of what functional programming is all about.

Keep in mind that tilly's post is not really about the same kind of functional programming though. Its a classic post, dont get me wrong, but its just not the same thing.

As for Haskell and other such "pure" functional languages, I have never really liked them. Not having been a Comp Sci or Math major I found some of the syntax and paradigms to be pretty difficult to get my head around initially since i lacked a solid background in the underlying concepts (especially since I was doing it for fun and not for profit). Also, IMO Haskell is sometimes just too strict, I mean its a nice idea to model things like I/O in a side effect free way, but the fact is that when writing to a disk, you really are going for the side effect. I kinda think it just goes too far.

I would look into other not-so-pure functional languages too. Erlang is a favorite of mine, it looks alot like Prolog and is therefore sorta declarative, but is not so much about backtracing through a db of rules. It has single assignment variables, and uses recursion as its prefered means of iteration. While not as pure as Haskell, etc. it still has some valuable lessons to teach the curious programmer.

Also, and this has been mentioned here too, Standard ML is a great language for learning the functional paradigm. You can still do imperative stuff in ML if you want, and it has a pretty cool module system called functors. Its syntax is not as obtuse (to non-functional programmers) as some of its derivatives (OCaml, Caml, etc). It has an intensly cool type inference system (for more info on that read Dominus's article on Strong Typing in Perl chapter14 onward talks alot about ML's type inference system and why its sooo cool). There are a number of good ML books out there, and plenty of online info, most of which is pretty solid.

And dont forget about Perl! Perl is truely a multi-paradigm langauge, and can do functional pretty well. I once wrote a side-effect free, assignment-free perl module after reading too many books/sites about functional programming. I posted it on my scratchpad if you care to look, almost 300 lines and not one '=' operator. Of course it's pretty inefficient and largely useless in any real-world scenario, but hey this is functional programming we are talking about, so purity is paramount!

Anyway, enjoy your foray into the world of functional programming, IMO its one of the most valuable tools you will (almost) never use :-)