This really depends. The usual rule of thumb is that a runtime exception (at least in pure code) is for bugs in the code and explicit methods like Maybe are for bugs in the input. So if getting a Nothing from your map means your own code is broken, an exception is perfectly fine; if it means your code was called wrong, you want to just return a Maybe.
In practice, most of the time, you end up either coming up with a default or returning the Maybe. This is greatly helped by the fact that just propagating Maybe value is really easy because Maybe is a member of a bunch of standard typeclasses like Applicative, Alternative and Monad. Thanks to this, I've found most of my code follows a simple pattern: it pushes the maybe values through until it has a meaningful default. This is safe, simple and fairly elegant. At some point, I either pattern match against it or use a function like fromMaybe, which then allows me to plug everything back into normal code.
From this description it sounds like Maybe is similar to checked exceptions in ways I didn't even realize when I wrote my comment. The difference is that Haskell's syntax is pleasant and concise to work with.
It would be really annoying if Java's Map type threw a checked exception when you called get() because try/catch is so verbose and difficult to refactor around. But if it weren't annoying, it would probably make the API better and save me from shooting myself in the foot.
In practice, most of the time, you end up either coming up with a default or returning the Maybe. This is greatly helped by the fact that just propagating Maybe value is really easy because Maybe is a member of a bunch of standard typeclasses like Applicative, Alternative and Monad. Thanks to this, I've found most of my code follows a simple pattern: it pushes the maybe values through until it has a meaningful default. This is safe, simple and fairly elegant. At some point, I either pattern match against it or use a function like fromMaybe, which then allows me to plug everything back into normal code.