Moutain Lion - New line character in notification
It's not clear how you are trying to display the notifications, but this works for me:

terminal-notifier -message $'a\nb'


-title $'a\nb' is not displayed on multiple lines though (even if you replace \n with NEXT LINE (NEL)).