If you are "given a velocity" then you are given a direction- a vector tangent to the sphere in the direction of motion. Every great circle is the intersection of the sphere with a plane through the center of the sphere. You can think of that plane as generated by two lines- the line from the given point to the center of the sphere and the line in the same direction as the velocity vector.
Let's say you are given and your sphere has radius R. Then in Cartesian coordinates, the point is and the vector is . The cross product of that with the velocity vector is a normal vector to the plane and you already know one point.