How to design a "web spider" with state in Haskell?

Don't try to replicate to many object-orientation.

Just define a simple Browser type that holds the current URL (per IORef for the sake of mutability) and some IO functions to provide access and modification functionality.

A sample programm would look like this:

import Control.Monad

do
   b1 <- makeBrowser "google.com"
   b2 <- makeBrowser "stackoverflow.com"

   links <- getLinks b1

   b1 `navigateTo` (head links)

   print =<< getHtml b1
   print =<< getHtml b2

Note that if you define a helper function like o # f = f o, you'll have a more object-like syntax (e.g. b1#getLinks).

Complete type definitions:

data Browser = Browser { currentUrl :: IORef String }

makeBrowser  :: String -> IO Browser

navigateTo   :: Browser -> String -> IO ()
getUrl       :: Browser -> IO String
getHtml      :: Browser -> IO String
getLinks     :: Browser -> IO [String]

The getUrlContents function already does what goto() and getHtml() would do, the only thing missing is a function that extracts links from the downloaded page. It could take a string (the HTML of a page) and a URL (to resolve relative links) and extract all links from that page:

getLinks :: String -> String -> [String]

From these two functions you can easily build other functions that do the spidering. For example the "get the first linked page" example could look like this:

getFirstLinked :: String -> IO String
getFirstLinked url =
   do page <- getUrlContents url
      getUrlContents (head (getLinks page url))

A simple function to download everything linked from a URL could be:

allPages :: String -> IO [String]
allPages url =
   do page <- getUrlContent url
      otherpages <- mapM getUrlContent (getLinks page url)
      return (page : otherpages)

(Note that this for example will follow cycles in the links endlessly - a function for real use should take care of such cases)

There only "state" that is used by these functions is the URL and it is just given to the relevant functions as a parameter.

If there would be more information that all the browsing functions need you could create a new type to group it all together:

data BrowseInfo = BrowseInfo
     { getUrl     :: String
     , getProxy   :: ProxyInfo
     , getMaxSize :: Int
     }

Functions that use this information could then simply take a parameter of this type and use the contained information. There is no problem in having many instances of these objects and using them simultaneously, every function will just use the object that it is given as a parameter.

As you describe the problem, there is no need for state at all:

data Browser = Browser { getUrl :: String, getHtml :: String, getLinks :: [String]} 

getLinksFromHtml :: String -> [String] -- use Text.HTML.TagSoup, it should be lazy

goto :: String -> IO Browser
goto url = do
             -- assume getUrlContents is lazy, like hGetContents
             html <- getUrlContents url 
             let links = getLinksFromHtml html
             return (Browser url html links)

It’s possbile to have 2 or “browsers” at once, with its own separate state:

You obviously can have as many as you want, and they can't interfere with each other.

Now the equivalent of your snippets. First:

htmlFromGooglesFirstLink = do
                              b <- goto "http://www.google.com"
                              let firstLink = head (links b)
                              b2 <- goto firstLink -- note that a new browser is returned
                              putStr (getHtml b2)

And second:

twoBrowsers = do
                b1 <- goto "http://www.google.com"
                b2 <- goto "http://www.stackoverflow.com/"
                putStr (getHtml b1)
                putStr (getHtml b2)

UPDATE (reply to your update):

If Browser has a state, it can send HTTP Referer header and cookies while hiding all mechanics inside itself and giving nice API.

No need for state still, goto can just take a Browser argument. First, we'll need to extend the type:

data Browser = Browser { getUrl :: String, getHtml :: String, getLinks :: [String], 
                         getCookies :: Map String String } -- keys are URLs, values are cookie strings

getUrlContents :: String -> String -> String -> IO String
getUrlContents url referrer cookies = ...

goto :: String -> Browser -> IO Browser
goto url browser = let
                     referrer = getUrl browser 
                     cookies = getCookies browser ! url
                   in 
                   do 
                     html <- getUrlContents url referrer cookies
                     let links = getLinksFromHtml html
                     return (Browser url html links)

newBrowser :: Browser
newBrowser = Browser "" "" [] empty

If Browser has no state, the developer is likely to pass around all current URL/HTML/Cookies -- and this adds noise to scenario code.

No, you just pass values of type Browser around. For your example,

useGoogle :: IO ()
useGoogle = do
              b <- goto "http://www.google.com/" newBrowser
              let b2 = typeIntoInput 0 "haskell" b
              b3 <- clickButton "Google Search" b2
              ...

Or you can get rid of those variables:

(>>~) = flip mapM -- use for binding pure functions

useGoogle = goto "http://www.google.com/" newBrowser >>~
            typeIntoInput 0 "haskell" >>=
            clickButton "Google Search" >>=
            clickLink "2" >>=
            clickLink "3" >>~
            getHtml >>=
            putStr

Does this look good enough? Note that Browser is still immutable.