How to Design Programs in Haskell and Other Functional Languages

I write my answer mainly with Haskell in mind, though many concepts apply equally well to other functional languages like Erlang, Lisp(s), and ML. Some even apply (to some extent) to Ruby, Python, Perl and Javascript.

How do people write functional programs? How do they start?

By writing functions. When you are doing functional programming, you either are writing main, or you are writing a helper function. Sometimes your main goal might be to write a data type with various relevant functions that operate on it.

Functional programming is very well suited to both top-down and bottom-up approaches. Haskell strongly encourages writing your programs in high-level language, and then simply defining the details of your high-level design. See minimum, for example:

minimum    :: (Ord a) => [a] -> a
minimum xs =  foldl1 min xs

The function to find the smallest element in a list is written simply as a traversal over the list, using the min function to compare each element with the "accumulator", or current minimum value.

Are there design patterns for functional languages?

There are two things that could be equated to "design patterns", imho, higher-order functions and monads. Let's talk about the former. Higher-order functions are functions that either take other functions as input, or produce functions as output. Any functional language generally makes heavy use of map, filter, and fold (fold is often also called "reduce"): three very basic higher-order functions that apply a function to a list in different ways. These replace boilerplate for loops in a beautiful way. Passing functions around as parameters is an extremely powerful boon to programming; lots of "design patterns" can be accomplished simpler by using higher-order functions, being able to create your own, and being able to leverage the powerful standard library, which is full of useful functions.

Monads are the "scarier" topic. But they're not really that scary. My favorite way to think of monads is to think of them as enveloping a function in a bubble and giving that function superpowers (that only work inside the bubble). I could elaborate, but the world doesn't really need yet another monad analogy. So I'll move to quick examples. Suppose I want to use a nondeterministic "design pattern". I want to run the same computation for various different inputs at the same time. I don't want to choose just one input, I want to choose them all. That would be the list monad:

allPlus2 :: [Int] -> [Int]
allPlus2 xs = do x <- xs
                 return (x + 2)

Now, the idiomatic way to perform this is actually map, but for illustration's sake, can you see how the list monad allowed me to write a function that looks like it operates on one value, but endowed it with the superpower to work on every element in a list? Other superpowers include failure, state, interacting with the "outside world", and parallel execution. These superpowers are very potent, and most programming languages allow functions with superpowers to rampage all around. Most people say Haskell doesn't allow these superpowers at all, but really, Haskell just contains them in monads so their effect can be limited and observed.

tl;dr Grokking higher-order functions and monads is the Haskell equivalent to grokking design patterns. Once you learn these Haskell concepts, you start thinking "design patterns" are mostly cheap workarounds to simulate the power of Haskell.

Are methodologies like extreme programming or agile development applicable for functional languages?

I don't see anything that ties these management strategies down to any one programming paradigm. As phynfo stated, functional programming practically forces you to do function decomposition, breaking a large problem into subproblems, so mini-milestones should be a piece of cake. There are tools like QuickCheck and Zeno to test or even prove properties about the functions you write.