user-friendly search strings

Hey everybody. I'm sure most of you have had to deal with this problem at
some point, and I'd like to get an idea of a good way to handle it.

What I have is a column of strings that users will be doing substring
matching against. While an ilike clause takes care of most of my problems,
some of these strings aren't so easy for users to type - e.g. "Björk", "0°
North", "8½ Souvenirs", etc. In addition, some are ambiguous - e.g. "3 Dog
Night" vs. "Three Dog Night."

What I want is to make matching against this column to be user friendly,
so that, regardless if a user searches for "bjork" or "Björk", they match
against "Björk". I also want searches for "3 dog night" and "three dog
night" to have the same results.

I don't suppose any of you have a magic fuzzy-matching searchification
stored proc lying around?