It seems to be a question recurring over and over again: how to quote a string for the shell. The shell is a quite powerful tool with lots of useful expansion mechanism. But therefore, you also need to take a bit of care when using it.
In general, if you need to call a command immediately, it's better not to go via the shell, but call execve(2) directly. But in some case, you're supposed to output a script to be executed later. One such example is the cvs queue, where commands accessing a remote cvs(1) repository are queued till the machine (like your laptop) is online again.
My take here on quoting is to replace every single-quote (') by the sequence single-quote, backslash, single-quote, single-quote ('\'') and put the result into single quotes.
In perl(1) that reads as follows.
# $message contains the raw message $message =~ s/\'/\'\\\'\'/g; print <<"EOI" # ... $cvs ci -m '$message' EOI