I bought an Apple Watch from target. When I went to activate cellular at Verizon, I was told it has an activation lock on it. How do I get that removed?

If you can perform all the steps in the 'Before you buy a watch from a third-party' section of:

What to do before you sell, give away, or trade in your Apple Watch, or buy one from someone else - Apple Support

then it its not Activation Locked. However, maybe it is "locked" to another carrier's network besides Verizon.

How to unlock your iPhone for use with a different carrier - Apple Support'

Also see:

Set up cellular on Apple Watch - Apple Support

Apple Watch - Carriers - Apple

Did you mean to buy a used or refurbished watch from Target? Are you sure Verizon said it was "Activation Locked" or did they just mean it needs to be activated on their network? Make sure that you have an eligible cellular service plan with a supported carrier. Your iPhone and Apple Watch must use the same carrier,* and you must be within your carrier's network when you set up cellular on your watch. For more info, see:

Set up cellular on Apple Watch - Apple Support

Activation Lock is designed to prevent anyone else from using your Apple Watch if it's ever lost or stolen.

About Activation Lock on your Apple Watch - Apple Support

Activation Lock is an anti-theft feature that cannot be bypassed. Only the previous owner can remove the lock. Apple will not help you find the previous owner. If the previous owner cannot or will not remove the lock, then the watch is useless to you or anyone else. Take it back to Target and get a refund.