Python 792 781 Chars

There are a lot more and much better answers from when I first saw this, but I did waste a lot of time on my python script so I am going to post it any way, it would be awesome to see suggestions to further shorten it,

x,n,l,r,m,s,t,u,w,a,b,y,j="give|Never gonna |let you down|run around and desert you|make you cry|say goodbye|tell a lie and hurt you\n|I just wanna tell you how I'm feeling\nGotta make you understand\n|\nWe've know each other for so long\nYour heart's been aching but\nYou're too shy to say it\nInside we both know what's been going on\nWe know the game and we're gonna play it\n|We're no strangers to love\nYou know the rules and so do I\nA full commitment's what I'm thinking of\nYou wouldn't get this from any other guy\n|And if you ask me how I'm feeling\nDon't tell me you're too blind to see\n|\n(Ooh|, ".split('|')
g=x+' you up'
p='\n'+'\n'.join([n+z for z in (g,l,r,m,s,t)])
o=y+j+g+')'
O=y+')\n'+n+x+j+'n'+n[1:]+x+'\n(G'+g[1:]+')'
print a+u+p+w+b+p+p+o+o+O+O+'\n'+w+u+p*3

After seeing ugoren's answer I tried to compress the program itself in a couple of naive ways, but I guess I have no idea how to compress a string by hand (i.e. not using zlib etc.)