What to do if my undergrad hasn't prepared me well for grad school? I will soon graduate with a data science MSc and am specializing in AI/machine learning, in which I would like to do research. I can read, understand and apply research papers pretty well, but I don't feel like I have the background to actually do research. When an author derives something, I sometimes need a few minutes to make sure that the math is sound. This comes from the fact that my undergrad school is only really good at teaching software development, and most of the courses I could take ended up being linked to that, neglecting the mathematical side of things.

The most worrying thing is that I don't feel completely sure about my choice of fields, since I have not been exposed to serious courses in most subjects that interest me. My bad results in math years ago were not from lack of interest, and I would have liked to take some serious courses in math and related areas, and give myself some time to decide what to do. This will probably become harder when I enter the job market. I may also have good PhD opportunities in machine learning through my job, which makes it even riskier to leave and start another degree without being sure I will like the field and do well in it.

I have started working through textbooks in various areas (linear and abstract algebra, statistics, machine learning), but without a clear plan, it's hard to prioritize self-study and focus effectively. There are too many interesting areas and not enough time and energy to learn all of them. Finally, I can't be sure that I am learning well or just getting the illusion of progress, since a set of textbooks can't replace a structured degree program.

How can I make sure that I'm ready and in the right field when I start applying for grad school? I'm not afraid of "losing" a few years to get another degree, if that's part of the answer.
Just a guess, but the guess is that you are uniformly underestimating your own skills and the quality of your education. You say "When an author derives something, I sometimes need a few minutes to make sure that the math is sound." Well, it might take me hours or days. 

You are undecided about field and find a lot of interesting things that you might study. This is natural, but could be a block, since doctoral study is all about specialization. So, pick something that seems the most interesting to you and that seems to have some future possibilities. Apply to a program that is good in that field and find an advisor. You will be led toward specialization over a year or so and your research will lead you deeper. 

There are two hard parts to research (well, maybe three). You need to find a suitable problem and you need to find a way to resolve it. (The third is, in some fields, coming up with a methodology for the resolution). An advisor can be helpful, especially, in coming up with a problem - or at least suggesting several, or pointing you at places that might be hiding problems. 

But you won't know until you get into the thick of it. 

And, for all of the "other" cool things that you leave behind by specializing, they aren't closed off from you forever. But first, get a doctorate so that you again have freedom to pursue whatever interests you. 

Some people (myself) have changed fields quite drastically for many reasons. Some because of the academic economy at the time, but others (not me) have actually invented new fields. Some just followed their thoughts and branched off into a new area. 

As a researcher you are currently unformed. The forming will come through practice and with the (hopefully good) guidance of an advisor. 

Narrow your focus a bit. Apply to a good school. Find a good advisor. Work hard. Hopefully success will come, but satisfaction probably will in any case.