Tones are probably the hardest thing about learning Mandarin as a second language, more difficult than the rest of the pronunciation or even the characters, and unfortunately in my experience it's correct what one of the other posters said that tones are not something that improves over time - I know plenty of "foreigners" who have studied and spoken Chinese for years, but never really gotten the hang of tones. What others have also said about native speakers not really caring about tones is mostly true, in that they just won't really expect you to get tones correct, but it will still cause issues in understanding - I'd say it's somewhat akin to a non-native speaker of English with bad grammar.
While there's no real substitute for hard work and practice, I do think that a large part of the problem with foreigner's tones is that they're taught incorrectly (which is nobody's fault - more on that later). I don't claim to be an expert myself but here's my understanding from 10+ years of studying Mandarin.
First of all, you won't really be able to easily hear the difference in tones until you're able to say them correctly. That might be discouraging, but it's a bit like trying to hear differences in a letter that you personally cannot say (which Chinese has a few of as well). Until you can do it yourself, you're not going to be able to easily pick up on what other people are doing, because language is a physical act and we feel the difference between sounds just about as much as we hear them. So my first advice is to focus on learning to say the tones before struggling too hard to differentiate them.
So that's great, you might say, but that's exactly my problem! How do I say the tones if I've never heard them? So here's my second bit of advice - tones occur almost entirely in the throat. I don't have a PhD in linguistics, but I believe this is also why Chinese sounds tend to occur further forward in the mouth - like you may have noticed that native speakers tend to make the "R" sound more like a "zhr", that is, not so deep and guttural when compared to the hard American "R", or even the softer British one. So put your hand on your throat when you say the letter "R", or even the letter "L", or "I" and "U" (these are also vowels and consonants which native Chinese speakers struggle with, by the way). The part of your throat that is making these L R I & U sounds (I'm assuming you're a native English speaker, by the way, as your post is in English) is the same part that you're going to use to make tones.
Now when you say these sounds, you should be able to feel which part of your throat is making the noise - R is higher in the throat, closer to the chin, whereas L should be deeper, and I higher than U as well. Somewhere around where you feel the R and I sounds is where you're going to make first tone - just hold the tone flat, and you should feel the strongest vibration high in your throat, close to the chin.
Now here's the confusing part - for second tone, the so-called "rising" tone, you're going to move the sound back in your throat, let's say from the "I" to the "L". In fact, saying the word "ill" should create a similar effect. Start with the sound at the top of your throat, near the chin, and move it back in your throat, towards the chest. Do this while also raising the pitch and you should be making a correct second tone.
For third tone, you're going to start out more or less like you did for second tone, but when the sound reaches the bottom/far back in your throat, you reverse direction - almost like you're clearing your throat. You should feel/hear a kind of wobbly/gargling noise in the back of your throat, almost like a turkey's call. If you hear that sound, that's basically the sound that Chinese speakers are listening for when they hear third tone.
Fourth tone is clipped, forceful and sharp. You make it by doing essentially the opposite of second tone, moving from somewhere in the back/middle of the throat up toward the chin, like a forceful expulsion of air. Think a bit like yelling a command at somebody, like in the military - you're pushing the air out.
We do actually use tones in English, just in a different way, although I didn't find the concept quite as helpful with improving my tones. Second tone is a bit like the questioning tone of voice, or maybe like how somebody with the stereotypical California valley-girl accent raises the end of every sentence? Y'know? Whereas fourth tone can sound kind of angry. The reason I didn't find this so helpful is that tones in English are made really obvious when we use them, because we're trying to express emotional content and so want to make sure we're being absolutely clear, whereas tones in Chinese are much more subtle. So if you're listening for every second tone to sound like a question and every fourth tone a command, you're gonna have a bad time.
Also, I didn't mention neutral tone but it's pretty obvious, just say the sound normally, without any inflection.
Anyway, hope that helps! It makes sense to me but I'm not sure if it will make sense to anyone else. It definitely helps to have an in-person class but like one of the other responses said, you just have to find somebody patient. There are Chinese speakers everywhere and in my experience they're very friendly and eager to teach somebody who wants to learn about their language or culture. Good luck and 加油!