Always, before executing commands, backup your entire database (and prepare for quick recovery, having putty.exe at hand + your ssh login + the command to dumb the mysql-database).
The mysql-command we need to remove rel="nofollow" is called REPLACE.
I used sqlfiddle.com to build a sample table 'qa_posts' with data, and (see left panel) added an UPDATE in the end that removes the nofollow tags. It is:
UPDATE `qa_posts` SET content = replace(content, ' rel="nofollow" ', ' ') where instr(content, ' rel="nofollow" ') > 0;
Here is the fiddle to see and test yourself: http://sqlfiddle.com/#!2/2a7d7/3
Note: I DO NOT guarantee any correctness of the syntax above, before using this command do your test with a dummy! If you don't know what you are doing, don't do it ... otherwise all your database can be lost!
Edit: The query above will not remove all nofollows as some come just before a closing >. This is the 2nd query you need to remove those as well:
UPDATE `qa_posts` SET content = replace(content, ' rel="nofollow">', '>') where instr(content, ' rel="nofollow">') > 0;
See also mysql-example in sqlfiddle.
