This is basic epidemiology. When medical professionals notice that a group of people with some characteristic in common, are being seen for a similar disease, they ask if there's a connection. In this case, several people in Wuhan were diagnosed with severe pneumonia, and the doctors noticed that they worked in the same location.
Three adult patients presented with severe pneumonia and were admitted to a hospital in Wuhan on December 27, 2019. ... Her occupation was retailer in the seafood wholesale market. ... He had been a frequent visitor to the seafood wholesale market.
--A Novel Coronavirus from Patients with Pneumonia in China, 2019
You're more likely to follow up when the disease is unusual or severe, and when the connecting factor is unusual or suspicious. In this case, the severe pneumonia was presumably unexpected, and live animal markets always have potential for disease transmission.
(In fact, it's quite possible that the virus had been circulating in the region for weeks before this cluster was noticed, and that previous cases had not been surprising enough to trigger the research needed to identify a new virus; though it's also likely that the medical personnel in Wuhan had noticed that there were an usually high number of pneumonia cases and were already looking for a connection.)
See also the answers to How did scientists discover HIV?. Old-fashioned epidemiology is always critical.
The same article explains how the virus was sequenced:
Bronchoalveolar-lavage fluid samples were collected in sterile cups to which virus transport medium was added. ... RNA extracted from bronchoalveolar-lavage fluid and culture supernatants was used as a template to clone and sequence the genome. We used a combination of Illumina sequencing and nanopore sequencing to characterize the virus genome.
... supernatant from bronchoalveolar-lavage fluid samples was inoculated onto the apical surface of the cell cultures. ... After three passages, apical samples and human airway epithelial cells were prepared for transmission electron microscopy. ...
So briefly, they took patient samples, grew them on cultured cells, used electron microscopy to check the kind of virus. They sequenced fluid (not cells, since the virus would be secreted into the fluid, making it a relatively pure source of virus RNA) and then sequenced using a standard high-throughput sequencing approach; knowing the likely kind of virus would make this easier but isn't essential. There would have been lots of human RNA in the sequence, but it's easy to bioinformatically separate that out and limit your analysis to the viral sequences. The virus isolate was also not essential for the identification; knowing the sequence is the critical information today. But having a virus isolate certainly makes all the subsequent work much easier.
This is pretty standard modern molecular biology, not an esoteric skill.