I think Feynman had a good answer to this question:
https://www.youtube.com/watch?v=Q1lL-hXO27Q
Essentially the issue with this question is that the usual ways you'd answer that question all seem unsatisfactory, and the key to "answering" the question is to understand not magnetism, but why magnetism seems mysterious and all the answers seem unsatisfactory. Like, actually understanding magnetism in the sense of having read and understood the Feynman lectures definitely helps but that's no good to a layperson.
And the answer to that as I understand it is that we always understand things in terms of other things we understand. When you see a process you don't understand and learn how it's caused by a process you do understand, you will feel satisfied, like you understand the process. If you don't understand a very weird thing but you find a good analogy to something you are familiar with, you will feel like you understand the thing. The thing is, that's all a feeling. Hopefully the feeling correlates to having an internal model of the thing that's closer to its nature than your previous internal model, and to being able to make better predictions about the thing's interactions, and it usually does because the brain is well-made, but it's still two different things and you can have a feeling of understanding without an improved model or predictions and vice-versa.
And the issue with magnetism is that unlike most other physical things we run into in daily life, it's a fundamental force that has macroscopic effects our brain didn't really evolve to be familiar with, and the best explanations for those effects require going directly to the fundamental force, and the fundamental forces is something that's very very unfamiliar to anyone who hasn't done university-level physics. If I say "electromagnetism explains how solid objects don't just go through each other" your response won't be "but I don't understand electromagnetism!", it will be "wait, did we need an explanation for why solid objects don't go through each other?". We have an innate sense of how solid objects interact at our scales that feels like it requires no extra explanation. And any behavior of solid objects that does require extra explanation usually involves explanations just one level deeper in the causal chain, which is close enough to what we are familiar with that we can understand it. And as explanations go deeper the causal chain things become weirder and weirder, but as a student of physics you go gradually, get used to each step and when a step becomes familiar enough it helps you "understand" the next one. So at some point you may end up feeling like you understand electromagnetism as a fundamental force, but it took a lot of work to get there (and that feeling my be fairly fleeing and changeable).
We don't have an innate sense of how magnetism works, and the actual explanations for how it works aren't just one step removed from things we do have an innate sense of. It's legitimately the case that the answer to "Why do magnets work like that" is "electromagnetism", and if you don't understand electromagnetism (which, as a layperson, you don't) you're screwed. There is no phenomenon or analogy that you have an innate sense of that's enough like magnetism to provide understanding. You straight-up have to do university-level physics until the concepts in question start becoming familiar.
In a way your question is even worse, because look:
What does it mean for them to be composed of “lines of force”? What is the mechanism of that force? What is actually going on in a magnetic field that the space outside of a magnetic field lacks?
You're kind of asking "what component parts is the fundamental force of magnetism made of and how to they interact to make it behave that way", aren't you. And the issue with this is that in the current standard model, there are no such component parts and causes; that's what "fundamental" means. Now, we know physics isn't a solved field so in practice there may indeed be extra explanatory steps out there to be found. But 1) they'll be even weirder than the current thing you're asking about is. They won't help you understand, they'll just confuse you further and seem like worse ad-hoc gobbledlyremoved than "fields" and "force" do. They'd only help you understand if you'd studied enough quantum physics for it to feel familiar and maybe almost-understood. And 2) at some point we kind of do have to hit an explanation that has no further explanation, something that's not made of something else. Maybe it's worth it for you to think about what that might be like. You'll probably still feel the urge to ask "but what is that basic thing made of, what explains that explanation?" but you'll have to accept that this question is that of a brain that evolved in an environment where everything is made of something else and things have nigh-infinite causal chains explaining that they are what they are. It just might not be very good at thinking about a situation where that's not the case.
I think a useful way to think about it is that your perceptual brain isn't in the business of making you see, or hear, or anything like that - it's in the business of giving you an accurate-enough-to-be-useful idea of what's around you. You see the world as being sharp and stable and consistent even though the literal visual signals going from your eyes to your brain aren't... because the world is sharp and stable and consistent. Or at least it's enough those things that it was useful for the brain to evolve to generate that specific perceptual experience. The signals coming from your eye are just (some of) the information the brain uses to generate that experience.