I have a Joomla site with about 500 users, and I also have a Constant Contact account with about 800 "users". Some of the site users are on my CC list but not all of them.

Is there a way to add this plugin and then link the current site users that are on my CC list to their profiles?

If I understand you correctly, the profile "link" to Constant Contact is solely from the email itself.
There isn't really any linking happening, simply a call to your CC account from the user profile. If CC has the email in your account, they will see what lists they have subscribed to.

They can also choose to sign up from their profile as well change their list choices.

Does this help?

That does help, so everyone that has a user profile e-mail that matches their CC e-mail address, this plugin will work for. They will be able to update their CC info from the plugin.

Can they also update their CC e-mail from the plugin?

Sorry for the late response...

Yes, updating their email on your site, will update Constant Contact also.