You can simply take the media from the one filter and put it into the new one. Should not br any cycle at all if you do that.
Media can be a number of things. Sponge is good, can be cut to fit, and can last for years. The best kind is the kind made for filters. Aqua Clear sponges are terrific and last for many, many years. If you go for ordinary sponges, you may find they don't last nearly so well. But try to find sponge with a coarser texture, as very fine textured sponge will clog fast and need cleaning more often.
Lava rock in small pieces makes very good biomedia too, as good as many ceramic bio media. And you can buy the ceramic type biomedia online too, pretty much all media can be bought online if you don't have handy stores. Even perlite, the kind used for plants, would work, though it's so light, you'd have to make sure it was tightly tied in a mesh bag and underneath some other heavier layer to prevent it from floating. It has a vast surface area too.. but it does float, given any chance to do so.
Filter floss is terrific stuff too. You can use poly quilt batting or pillow stuffing instead, so long as it does not have fire retardant or mildew resistant treatment on it. Check labels, which should say if the stuffing has been treated. Fabric stores are a good place to look if you can. It can last for a surprisingly long time. I don't change mine until it is falling into shreds, and then only replace half of it at one time. It will turn grey, but that's ok, it still works fine.
You can also use those green scrub pads for non stick cookware. Don't need a dollar store, any place selling cleaning supplies would have them. Just be sure it does not say on the package 'not for aquarium use'.. as if it does, chances are it's been treated with something to prevent mildew.
I don't think I'd use gravel, it's just not as good as lava rock or genuine bio media is. That's because it's solid and does not have nearly so much surface area to offer for bacteria to colonize. Sponge would work better than gravel.
If you can only get floss, using that alone would work too, though you would have to replace some of it every so often. It does have a ton of surface area, and it's also an excellent water polisher. Just squeeze it out well when you clean it and put it back. But I think at least one other media that's more durable than floss is the best way to go.