How to implement an ADPLL in Verilog that locks onto an arbitrary sine wave?
Sine waves are easy.

Obviously, your PLL comprises a phase/frequency detector, a loop filter and an oscillator. Your NCO provides I and Q outputs, which make it easy to make a phase measurement of the input signal. (Two multiplication operations)

Think of this measurement as a vector, and the main thing we're concerned with is the angle of this vector (atan2 operation). This vector will be rotating (phase increasing or decreasing from one sample to the next) if there is a frequency error; the direction of the rotation tells you whether the frequency is too high or too low. Once you get the frequency matched, you can drive the output phase to the desired relationship to the input phase.

Is this enough of a hint to get you on your way?