I am using Android 6.0.1, so this may not work for some.
I used it for WhatsApp, see comment below.
Settings -> Notifications -> ADVANCED (at the top right) -> (Choose the app you want) -> (tap the little info icon at the top right) -> Notifications -> More settings -> Popup notification -> Always show popup
(see image below).
I tested that this setting is what makes the difference, since setting Only when screen "on" did not show notifications in locked screen.
But this is a setting from WhatsApp, as I could access it from within WhatsApp as well.
I could not find a setting from Android for doing this (neither on a per-app basis or as a global setting), so I wonder whether it is up to each app to have a setting like this. This makes this post partly an answer and partly a question!
Note: In Android 6, settings for Sounds is separate from Notifications.