Like, I know what the concept is (advancing the game frame-by-frame and making the perfect decisions on each frame), but literally how do you create such a run?

Here's a tutorial for that: http://tasvideos.org/TASHowTo.html If you have any questions, theres a forum with people that understand the whole TAS thing better than we do

It's easier than ever in BizHawk thanks to TAStudio, which has a graph for each frame since Power On and which inputs are active on each frame.

From there it's just a LOT of work. Good TAS runs don't appear out of thin air, and the ones you see published on TASvideos typically take months, sometimes years, to construct.