Miss Pico is on K-9 Advantix, which has the advantage of also helping with mosquitos (Heartworm and West Nile carriers). It's not natural, but it works amazingly well. Also, a few years ago we went hiking in the woods in Texas with about 30 dogs. The dogs not on Advantix or Frontline ALL had a bunch of ticks - Pico had none!.
Spraying your yard with pyrtherines (a pesticide made from daisies) seems to keep the fleas off your animals as well. Here in Oregon it is also useful because it keeps carpenter ants out of your house.
Pennyroyal herb is very effective against fleas, but it is really strong medicinally as well and can cause abortion and liver damage in humans (and presumably animals) if too much is taken internally. I'm honestly not sure it's any safer than Advantix. I used to put pennyroyal between the mattress pad and the sheet at the bottom of my bed where my animals liked to sleep to keep fleas out of my bed and it worked really well. Like I said, I use Advantix now.
Julie