Once you've unlocked him on a single character:
1. Legacy Page (Y key)
2. Global Unlocks -> Other
3. At the bottom, Compaions.
4. Unlock HK-51 for your legacy.
Now, once he's unlocked for your legacy you still have to spend credits or cartel coins for each new toon.
Basically, you unlock him for legacy first, then for each toon.
There is a 'HK-51 Republic' and 'HK-51 Empire' unlock because they unlock completely different (coding wise) companions. The two HK's, much like the two Treeks, have separate companion conversations depending on your side. -FabulousDoctor
I believe it's 1million credits in the legacy tab. I did quest on main and paid for 2 alts.
Yep it's a mil per toon.