"We'll be saying a big hello to all intelligent lifeforms everywhere, and to everyone else out there, the secret is to bang the rocks together guys . . . ." - From The Hitchhiker's Guide to the Galaxy, by Douglas Adams.
Rutherford's team didn't know much, but they suspected the atom was made of smaller pieces somehow. The prevailing model was the "Plum Pudding Model" - a lot of particles (to account for the ionisation and varying weights of atoms), all embedded in goo. So the obvious thing to do was to bang atoms together and see what the rubble looked like.
They knew (e.g. from electroplating) that an atom can be ionised (electrically charged), and in fact J J Thomson discovered the electron in 1897, while Ernest Rutherford described the proton/electron model of the atom in 1909.
So the obvious way to bang atoms together is to ionise some atoms (maybe from the electrodes of an arc lamp), and use a strong electric field as a gun to shoot them at other atoms (a gold foil sheet, beaten so thin it was only a few thousand atoms thick). Alternatively, he also used alpha particles (essentially helium atoms without electrons) which are emitted during spontaneous radioactive decay.
Once you collect enough bits of broken atoms (using a Wilson cloud chamber to see where they go and whether they have electric and magnetic components), you try to put the puzzle back together in a way that explains the outcomes you observed.
The killer result for Rutherford was that 99.9999% of protons went straight through the thinnest gold foil he could make, but a very few came straight back at him. He later said something like: "It was as though we had fired a twenty-inch shell at tissue paper, and it had bounced back.". His explanation in 1911 was that the atom was mainly empty, with a compact heavy nucleus and orbiting electrons.
