The most relevant HOWTO document on how to do this is in a PDF here: http://developer.infi.nl/daniel/Linking%20MySQL%20and%20MSSQL.pdf
I have mirrored it here: http://www.lucision.com/legal/rjurney/Linking%20MySQL%20and%20MSSQL.pdf
There is a truncated HTML version of this article on the same site, but it stops in the middle of the provider string.
Provider strings are important. You can find them, including one for MySQL, here: http://www.connectionstrings.com/
Now, I followed the directions in these tutorials and still could not get it to work. What made it work? I restarted SQL Server 2005 and it just all worked immediately, with a query like this:
SELECT * FROM OPENQUERY(LINKEDLUCISION, 'select * from mydatabase.tablename')
Queries of the format SELECT * FROM LINKEDLUCISION.mydatabase..tablename
still do not work. I dunno how to do these, but in my case we will be creating a VIEW that uses the OPENQUERY, so we are pretty much set.
Some people seem to use the API here: http://msdn2.microsoft.com/en-us/library/ms190479.aspx but I had no luck with it.