Complete the quest:
https://ffxiv.gamerescape.com/wiki/Color_Your_World
to unlock the ability to dye weapons and gear.

NOTE: Not all weapons or gear can be dyed.
If a gear piece or weapon can not be dyed, it will both have the description text of "Dyeable: No" in it's item window and no option to dye via the right click menu.

Normally, if you see someone with a gear/weapon that is dyed, but it seems the piece isn't dyeable, it is likely they are using a gear/weapon that has the same base appearance as the non-dyeable version, of which can be dyed.
So, look at the item's description window to make sure it's name.