If you have never done any other DNA testing, you probably want to begin with an autosomal, or "family" DNA test. That will help you with both lines, within about 5 generations. It is also usually the cheapest test.
The way it helps is that you'll get a list of people who match your DNA. Generally, the more DNA you share (measured in cMs), the closer your relationship is with the other person (with exceptions). Sometimes, all you will learn (besides how closely their DNA matches yours, is the other person's name or pseudonym and their email address, unless they have published a family tree that you can compare with what they know.
Y-DNA tests are for males only. A male carries Y DNA that is passed very specifically from father to son (usually would follow the surname, if the son is born in wedlock). You won't learn about the male's mother, or about his father's mother, or get any information concerning any females in the lineage from the DNA itself.
MT-DNA is similar, but for females, and follows you, your mother, to your mother's mother, and so forth.
I think there is a lot more science that I haven't learned about either Y or MT DNA, but I do have the impression that those tests are often better for going back much farther in time, and that finding genealogical information is harder because it's harder to locate records for ancient people.
Hopefully, if I have said anything that's too far off, one of the DNA gurus will set me (and you) straight.