(Links are to the pertinent points in the video)
00:15 Казахскся. ССР. A.D.2048
"Kazakh SSR A.D.2048"
(Russian script, Latin date)
02:49 Сиби́рь 1
"Balrog"2 (written backwards and mis-spelled3)
(looks like some kind of Aramaic or Hebrew script; Hebrew shown above)
This rather detailed article does give some insight in the ways they worked back then:
Designing 2D graphics in the Japanese industry
It doesn't go into details of fireballs, but does capture the various stages of development and their evolution over time. Especially the example of CRT vs. pixel is an interesting one.
The sprites in the 1982 Arcade Game Xevious were designed by Shigeki Toyama on graph paper by hand. They were admired in the day for their appearance, but they look pretty simple compared to subsequent games.
If you look closely at this screenshot, you can see that explosion is quite low detail, though precise use of colour and many frames of animation can ...
The question is way too broad to answer completely, but I'm pretty sure that in almost every case it was either graph paper (+ manual translation into hex, + manual fine tuning), or simple sprite editors. The latter existed on most platforms since at least the mid-80s (from personal knowledge), probably earlier.
Editing sprites with these editors was still a ...