I'm not entirely sure how to go about it, but I have a data structure that gives me
Speed
Bearing - Direction in the XY Plane
Z-Bearing - Direction in the Z Plane
How can I combine these into a 3 dimensional velocity vector?
I assume it's something like
Xvel = cos(bearing) * speed * cos(Z-Bearing)
Yvel = sin(bearing) * speed * cos(Z-Bearing)
Zvel = sin(Z-Bearing)
Buut I'm not entirely sure I'm correct.
You basically have it correct, presuming the interpretation of $Z$-plane (which doesn't quite make sense) works.
You do want
Zvel = speed * sin(Z-Bearing)though.See Spherical coordinate systems, where the usual convention is that $Z$-bearing $0$ is directly in the $Z$-direction, so flip mentions of
sinandcos(Z-bearing).