Found these instructions on the internet which fixed it for me:
To make Visual Studio adding 3rd party assembly or even your own assembly from other project in solution to GAC please do next:
Open Package.package from Package folder in SharePoint project.
Click Advanced in bottom area.
Click Add and chose which type of assembly you want to add.
In dialog select dll file, chec GAC or BIN, add safe controls and class resources entries if required. Click Ok.
Your assembly will be packaged to WSP, defined in manifest and deployed everytime.