Pot scrubbies are the way to go. Usually 6 in a pack for really cheap, they're easy to clean and have plenty of surface area for holding beneficial bacteria. Gravel can be used but like another person stated, there's better options for cheaper. If you had to use gravel, the best way would be to keep it inside a small pantyhose for easier cleaning, just pick up the pantyhose bag and wash.
