Will you be using the Linode DNS Manager (accessed through your Linode control panel)?
If yes, then you'd first login there and add your domain in the DNS Manager -- e.g., mydomain.com.
While you're there, think of a name for your Linode, e.g., stef.mydomain.com, and create an A record for it. That is your FQDN.
Next, login to your VPS via SSH and change the hostname to stef.mydomain.com. Exactly how you do this may differ according to the distribution you use. A little googling should help, e,g, "Ubuntu change hostname".
After changing the hostname, I'd suggest restarting the Linode to ensure the change persists across a reboot.
I believe the Linode nameservers are ns1.linode.com and ns2.linode.com. But I don't use Linode's DNS so I could be wrong

This information will certainly be in Linode's online documentation. Once you've confirmed the correct Linode namservers, set them at your domain registrar.
Give everything time to propagate and you should be good to go.