Return to Answer

Bash / Sed, 705 650 588 583 chars

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

Bash / Sed, 705 650 588 582 chars

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

Logic: Basically, simply using sed to replace repeated parts of the text. This song has lots of them.
But sed commands, like s/X/something/ tend to be repetitive, so I decided to use sed to shorten it.
So I feed sed with lines in the format Xsomething and it builds s/X/something/g from this. These commands are fed to sed again, to edit the song.
With this approach, the cost of a translation is very small, so I can use lots of them and remove almost all repetition from the text.

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.

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:

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.

Bash / Sed, 705 650 588 583 chars

Logic: Basically, simply using sed to replace repeated parts of the text. This song has lots of them.
But sed commands, like s/X/something/ tend to be repetitive, so I decided to use sed to shorten it.
So I feed sed with lines in the format Xsomething and it builds s/X/something/g from this. These commands are fed to sed again, to edit the song.
With this approach, the cost of a translation is very small, so I can use lots of them and remove almost all repetition from the text.

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 41 characters long. The other 547 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.

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

Bash / Sed, 705 650 588 583 chars

Logic: Basically, simply using sed to replace repeated parts of the text. This song has lots of them.
But sed commands, like s/X/something/ tend to be repetitive, so I decided to use sed to shorten it.
So I feed sed with lines in the format Xsomething and it builds s/X/something/g from this. These commands are fed to sed again, to edit the song.
With this approach, the cost of a translation is very small, so I can use lots of them and remove almost all repetition from the text.

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.

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