Jessica - for dogs you can give them a raw bone and let them have at it! It is a great teeth cleaning tool!

For cats, raw bones would work as well but cats tend to be finicky if it's not something they're used to. Brushing their teeth doesn't really work if the tartar is already there, it's really supposed to be a prevention thing. If it's really bad you probably will have to get them cleaned.