<p>I know a Haskell module name, but I can't figure out in what package it is defined. This is bad because I can't compile without a package exposing this module.</p>

<p>Specificaly it is Text.Regex that I can't locate, but I would like to know how to solve that problem in general.</p>

http://www.haskell.org/ghc/docs/latest/html/users_guide/packages.html
ghc-pkg find-module Text.Regex
But that only works for (a) recent GHCs, and (b) packages installed on your system.
You can also grep through the package file (e.g. /usr/lib/ghc-6.8.2/package.conf) to see what's installed.
You can also use either the haskell API search engines
hoogle
or the
hackage
search engine
hayoo
.
Text.Regex is in the package regex-base, and a few others built on top of it.