Note: this page was adapted from swordsmankirby's guide. Some strats may be outdated.
Single Fire
When using single fire, you normally fall down after the animation ends, but you can cancel the fall by floating up (A). To use fire again, you need to exhale by puffing (B) before being able to attack. This three-button sequence is known as fire canceling and looks like alternating fire and puffs, since the float animation is the shortest part of it. The whole time you're doing this you should be holding right (or left, if that's the direction you're moving in) to get the fastest horizontal speed. On the other hand, if you need to make the fire travel a shorter distance, hold the opposite direction.
One thing to note is that the lengths of the fires get shorter over time (see video), so each fire has a slightly different timing for the puff. After the third fire, they stop getting shorter. The length resets after some period of time, or if you hit an enemy with fire and don't kill it, e.g. hitting a miniboss, gordo, etc.
Double Fire
Long-thought to be faster than single fire before fire canceling was discovered, this powerup is useful for clearing long horizontal stretches, like the end of 4-4 or most of 5-1. Because we're not going to be frame-perfect on our fire cancels, double fire ends up having better horizontal speed. However, most of the time it ends up being slower than single fire for various reasons. For example, in a room with short horizontal segments (e.g. the second room of 1-2 or 5-1), there might be room for one or two single fires, but not a double fire. In many places, there is only one fire enemy, so getting double fire by respawning the enemy takes extra time.
The acceleration of double fire to its max speed depends on a few factors, but the simplest is your horizontal speed on the ground. The acceleration is slower if you're standing still, so it's slightly faster to take a step right before using double fire. Double fire usage follows a route to avoid landing on enemies because the recovery animation takes a long time. A lot of the time, the choice of whether or not you walk before firing is dictated by the route.
Curling Stone
Curling stone, which is used for the ice shard in 4-4, has slower movement than either fires, but getting it towards the beginning of 4-3 is still faster than all other alternatives. Curling stone starts at some initial speed and gradually decreases over time, so it's better to go in and out of curling stone repeatedly rather than stay in it for a long period of time. I believe that in a tool-assisted setting, the optimal amount of time spent in curling stone is 25 frames, but in real time it's probably better to stay for a little longer.
The video comparison shows curling stone's speed when starting from standing position versus running. In general, if you're running, it's 50% faster, but otherwise it's only 16% faster. To a lesser extent it depends on your vertical speed as well. In all settings, the speed decreases at the same rate.
Sliding
Perhaps the simplest thing you can do is to slide into loading zones. It saves probably something like a tenth of a second, but there are so many places to do so that it truly adds up.
Ledges are another place you can slide. In this comparison, the slide saved about three frames. In most instances, it's fastest to do what I call a "neutral slide," where you let go of the D-pad while sliding. When Kirby is in the air at a speed faster than his walking/running speed, he decelerates slower when there is no directional input. However, if the ledge is really high up, it's counterproductive to slide since Kirby will decelerate down to his walking speed, even if he was running prior to the slide. Sometimes, puffing after a slide is useful, like when you need to preserve some of your height after sliding or if there's an enemy directly in your way. Note that puffing needs to be done as early as possible in the slide animation, otherwise it won't save any time.
In the same way that the float animation preserves some of the fire's speed, one can slide and then start floating. This is useful in some places where a slide and puff don't cover enough horizontal distance, as shown in the above example.
Headbutting
While not exactly something that increases normal movement speed, headbutting is useful for maintaining running speed in the midst of enemy attacks. If you jump up into something and your vertical speed is high enough (i.e. not near the peak of your jump), the object you bump into will break or freeze in place. Because of weird hitboxes, this can even be done on objects already on the ground, but this isn't recommended for real-time speedrunning.