Do I need to connect the domain name and hosting together?
Yes. Depending on how the hosting was configured, the hosting company will want one of the two:
Simpler option: Move all DNS management to the hosting company. Go to your domain's control panel at GoDaddy, and change the nameservers to those provided by your hosting company.
Manual management option: Keep DNS management at GoDaddy, but go to your domain's DNS records control panel there and replace just the 'A' & 'AAAA' records with those provided by your hosting company. Make sure to change the records for both the bare domain and the "www" subdomain.
(For email hosting, you'll also need to change 'MX' records, possibly add some 'TXT' ones.)
Note that the DNS records have a "TTL" – time for which visitors can cache the record before checking for changes. For example, if the old (wrong) record had a TTL of 1 hour, and you just changed it, you'll have to wait up to 1 hour for the DNS changes to be fully active. Changing the nameservers for the entire domain, in particular, can take up to a day or two.
I reissued a new SSL cert, but I still cannot access the website via the internet.
Certificates do not tell visitors where to find your website; they're only used to confirm (certify) that the visitor has connected to the correct one. You need to have the domain working before the certificate will have any relevance.