Take a look at the wikipedia article for cartesian coordinates. And also Troigonometric functions (particularly the bits about unit circles).
To get a vector for an angle you use (as you have in your post) x = cos(angle)
and y = sin(angle)
(and don't forget that these methods take angles in radians, not degrees).
If you input an angle of 0 into that formula, you will have a trajectory that is traveling along the X axis. I'm guessing that your space-ship image is facing upwards? Hence the sideways movement.
The solution, of course, is to make your sprite point towards 0 degrees (ie: make it face right). Or, if you don't want to modify the image, add a fixed 90 degree offset to your angle before rotating, to compensate.
It gets a little more complicated than that - because XNA's SpriteBatch
uses a client (not cartesian) coordinate system, where the Y axis is flipped (Y+ goes down, not up). So the rotation formula stays the same, it is still mathematically correct. But you might need to swap whether the left/right key increases/decreases your angle (because the Y axis is flipped, the meaning of angles also gets flipped).