Bash / Sed, 705 650 588 583 chars
Logic:
The basic idea is simple replacement. Instead of writing, for example, Never gonna give you up\nNever gonna let you down, I write Xgive you up\nXlet you down and replace all X with Never gonna .
This is achieved by running sed with a set of rules, in the form s/X/Never gonna /g.
Replacements can be nested. For example, Never gonna is common, but so is gonna in other contexts. So I can use two rules: s/Y/ gonna/g and s/X/NeverY/g.
When adding rules, parts of the song texts are replaced by single characters, so it gets shorter. The rules become longer, but if the string replaced is long and frequent, it's worth it.
The next step is to remove repetition from the sed commands themselves. The sequence s/X/something/g is quite repetitive.
To make it shorter, I change sed commands to look like Xsomething. Then I use sed to convert this into a normal sed command. The code sed 's#.#s/&/#;s#$#/g;# does it.
The final result is a sed command, whose arguments are generated by another sed command, in back-quotes.
You can find a more detailed explanation in this link.
Code:
sed "`sed 's#.#s/&/#;s#$#/g;#'<<Q
LMWe'veKn each o!r for-o longPr hearHzchJbutP're2o-hy2-@Insidexe bothKxhaHCJonMWeK ! game+we'reZpl@
TMI justxanna _UFGotta QuXerstaXR
RM~Squp~letqdown~runzrouX+desertU~Qcry~sayCodbye~_z lie+hurtU
E(Ooh)~S, neverZSM(GV
F how=feelingM
Ht's been
%(Ooh, gV
Vivequp)M
~MNeverZ
K know
@ay itM
Qmakeq
qU
U you
PMYou
= I'm
+zX
ZCnna
Sgive
_tell
C go
2 to
!the
Jing
Xnd
z a
x w
- s
M\n`"<<_
We're no-trangers2 lovePK ! rules+so do I
A full commitment'sxhat=thinkJofPxouldn't get this fromzny o!r guyT
LAX ifqask meFDon't _ meU're2o bliX2-eeRRMM%%EELTRR
Notes:
The decompression engine is just 40 characters long. The other 543 are the translation table and compressed text. bzip2 compresses the song to 500 bytes (without the engine, of course), so there must be room for improvement (though I don't see how I'd add Huffman encoding or something like this cheap enough).
<<Q (or <<_) is used to read until a given character. But the end of script (or backquote expression) is good enough. This sometimes causes a warning.
Older and simpler solution, 666 chars:
sed "
s/L/ MWe'veKn each other for so longMYour heart's been aching butMYou're too shy to say itMInside we bothK what's been going onMWeK the game+we'reZplay itM/;
s/T/MI just wanna tellU how I'm feelingMGotta makeU understandR/;
s/R/M ~giveU up~letU down~run around+desertU~makeU cry~say goodbye~tell a lie+hurtU/g;
s/E/(Ooh)~give, neverZgiveM(GV/g;
s/V/iveU up)M/g;
s/U/ you/g;
s/+/ and /g;
s/K/ know/g;
s/~/MNeverZ/g;
s/Z/ gonna /g;
s/M/\n/g
"<<Q
We're no strangers to love
YouK the rules+so do I
A full commitment's what I'm thinking of
You wouldn't get this from any other guyT
LAnd ifU ask me how I'm feeling
Don't tell meU're too blind to seeRRM M(Ooh, gV(Ooh, gVEEL TRR