[h-e-w] search and replace across lines

[Lance Johnston]

Hi,

I'm wondering how I can do a search and replace across lines in emacs. 
For example, let's say I have the following text in a file:

 constant_text variable_text
 {
 ...

And I want to turn this into:

 constant_text variable_text
 {
   added_text
   ...

After trying for a while to get this to work, I think this question can 
be simplified to "How can I search across lines?", as I can't even get a 
search expression to span lines. I've tried all the obvious search 
expressions:

 constant_text.*$^{
 constant_text.*$\n{
 etc.

None of which seem to work.

Note that I'd like to simply do this using replace-regexp (i.e. via the 
minibuffer), but am not totally adverse to using lisp to make this happen.

Any ideas much appreciated.

Thanks,
Lance