When the notes played are on the same string, going higher, don't be in a hurry to play the higher note. The opposite way, again, leave it until the last moment to actually play the lower note, but in this direction, you can usually fret the lower note while the upper one is ringing.
There's also hammer-on and pull-off, which again, work on the same string, thus making it sound very much legato. This should be practised slowly, 60bpm, so one note per second is good for starters. Info. on how to perform both are readily available.
EDIT: one thing I gleaned from the video (thanks) was that you completely take off a finger that will be used very soon again on same string, same fret. Instead, just lift that finger enough to mute the note/string. It's then quicker to re-press. Actually, the playing isn't as staccato as you said in the post! Time and practice will turn it into legato - try playing it all a lot slower, so each note flows into the next. Use of metronome is key here, too.
If the notes are on different strings, chances are for beginner pieces that the next note will be on the adjacent string. Use as much tip rather than pad of fingers, so the notes don't get muted, either way.
Regarding the picking hand, it may be that you're anticipating plucking the next note, so stopping the existing one with the pick, or fingers if that's what you use. So tidy up your picking technique.
All that said - you're already aware that it's a problem, so lots of careful practice will eventually clear up the problem! A video clip of both hands would be of immense help, as I can only answer generally without one.