I have 20,000+ lines that I need to select-all and then be able to
insert a special character like ^ not normally found within the
document, at the beginning of every line, to allow me to then use Find
and Replace to insert a common string at the beginning of each line.
After doing this, I also need to be able to do the same thing at the
END of each line of text and run find and replace with a different
string on all 20,000 lines.
What is the most efficient way of doing this?

I think using sed might be more efficient since TextMate's handling of large files can be a little unreliable sometimes. Press option+command+r to bring up the Filter Through Command dialog and put this in the Command input box:

sed -e "s/^/\^/" -e "s/$/\^/"

That is, substitute a literal ^ (\^) for a beginning-of-line (^), and do the same for end-of-line ($).

That might be faster than the Find and Replace dialog on a big file. You can also store it as a command if you end up doing it a lot.

I hope that helps,

Brandon