I was not a strong swimmer before I went to college. I never had trouble with our swim quals when I was an enlisted Marine, but I couldn't hang with the lap swimming thing. ...Which they made me do endlessly at the academy.
Probably the thing that helped me the most was a pyramid-style interval workout. Usually 100-200m to warm up, some quick stretching, then sprint 50m, rest for 5-10 sec, repeat. I'd do that a couple times, then increase both the distance and the rest time to 100m/25-30 sec, and then increase both again. After I got up to 300m/1min of rest, I'd work my way back down before a very ssslllllooooowwwww 300-400m cool down.
Worked well for me, and if you combine that with a push-up/pull-up/ab workout right afterwards and running 3x/week, it'll put you into pretty kick-a$s shape.