Functional programming is a style of programming that emphasizes the evaluation of functional expressions, rather than execution of commands. The expressions in these languages are formed by using functions to combine basic values.
The functions alluded to in the title are mathematical functions. Mathematical functions have great strengths in terms of flexibility and in terms of analysis. For example if a function is known to be idempotent, then a call to a function which has itself as its argument, and which is known to have no side effects, may be efficiently computed without multiple calls.
A functional programming language is a programming language that supports and encourages programming in a functional style. Implementations of these languages are usually quite sophisticated about stack manipulation, since it is used so commonly.
Functional programming often depends heavily on recursion. The Scheme programming language even requires certain types of recursion (tail recursion) to be recognized and automatically eliminated by a compiler.
A powerful mechanism sometimes used in functional programming is the notion of higher-order functions. That is, functions that can take functions as arguments, and/or return functions as results. Higher-order functions have been studied long before the notion of functional programming existed, in the lambda calculus, a formalism which has influenced the design of several functional programming languages.
Chapter 4 - Functional Programming - of Raphael Finkel's Advanced Programming Language Design is an excellent introduction to and explanation of functional programming. Here's a link to the chapter, and here's AddisonWesley's [http://cseng.aw.com/book/related/0,3833,0805311912+20,00.html page for the book