How did scientists discover HIV?
HIV was identified as an infectious disease through classical epidemiology, and the virus was identified through classical virology.
I won't get into the epidemiology, but briefly it went pretty much as you'd expect -- a cluster of symptoms were identified, patient characteristics were analyzed, the contagious nature of the symptoms were recognized, all through standard approaches of patient tracking and so on.
As for the virus identification, that was long before modern molecular techniques were available.  It was even before PCR was commercially available!  So the techniques that were used were those of classical microbiology.
It seemed most likely that the agent was a virus rather than a bacterium (though every possible angle was covered), and just about every virologist tried looking for their favorite agent, but retroviruses also seemed like logical candidates and several groups tried isolating infectious agents from the blood of AIDS patients.
The two groups who were most successful were those of Luc Montagnier and Robert Gallo.  There turned out to be a lot of politics and personalities involved and I won't get into that.  Here are some comments from Montagnier summarizing the story:

There were only a few patients with this disease in France, but Gallo's idea that a retrovirus was the cause had already crossed the Atlantic. His idea was disseminated by a small group of clinicians and immunologists led by Jacques Leibowitch and Willy Rozenbaum. At the end of 1982, Françoise Brun-Vezinet, a former student of mine and a member of this group, proposed that we collaborate to discover if a retrovirus was the cause of this disease, now called AIDS.
We were ready to start because my laboratory was equipped to hunt for lymphotropic retroviruses in human T cell cultures.  ... On 3 January 1983, Françoise Brun-Vezinet obtained a lymph node biopsy from one of Rozenbaum's patients, ... I minced the lymph node, dissociated the fragments into single cells, and cultured the T lymphocytes with interleukin-2 and antiserum to human interferon. Fifteen days later, Françoise Sinoussi (by then Barré-Sinoussi) found the first traces of RT in the supernatant of the lymphocyte culture, indicating the presence of a retrovirus.  ... A few months later, I received a blood sample from a young hemophiliac (LOI) with full-blown AIDS, and blood and lymph node samples from a young gay man (LAI) with advanced Kaposi's sarcoma. The LAI virus could be isolated from the patient's blood cells and grew very quickly in the patient's cultured T lymphocytes, killing them as well as killing T lymphocytes from blood donors.
New evidence that this strange retrovirus was the cause of AIDS came from our team in the fall of 1983 and the winter of 1984 (7). We observed a high frequency of antibodies against the virus in lymphadenopathy patients, and noted the favored tropism of this virus for CD4+ T lymphocytes. Our results were still controversial, however, and we had difficulty in obtaining the funding needed to better characterize the virus and to develop a blood test. The tide only turned in France when Robert Gallo and his group in the United States made a similar discovery. In the spring of 1984, Gallo published more convincing evidence that HIV causes AIDS ...

--A History of HIV Discovery
Gallo's approach was similar -- focused on isolating replicating virus, more than performing the molecular biology that's become standard in the meantime.