It's not a coincidence that Underscore looks like Ruby, its creator has a Ruby background and similarly developed CoffeeScript along those lines. (Both of which are perfect for me as someone who uses Rails on the back-end.)
Yes, JavaScript never had anything resembling a decent utils library, so an elegant and popular implementation like underscore was heaven when it arrived. It's the usual problem of browsers evolving too slowly and fragmenting too much for something like Java's collections to emerge as a standard.
The situation has gotten better now, with even IE moving towards auto-upgrade, but it's still not feasible for JS core to ship with large, frequently-updated, JS libs. The closest thing is Node's standard library, but that's not going to be ubiquitous in browser's anytime soon.
"what should be a part of the language and what shouldn't"
In the absence of a standard library, you end up with a dozen competing libraries trying to fill the void, and that stifles end-user applications.
We saw that a few years ago with the DOM. For the first ~8 years of JS, there was no significant DOM library, so app developers had to suck up the unfriendly raw DOM API. Then the toolkits started to emerge, giving way to huge fragmentation between jQuery, Prototype, MooTools, Dojo, and YUI. Suddenly libraries were jQuery plugins or MooTools plugins and your app was using the jQuery stack or MooTools stack. So the next 8 years of JS saw vast effort duplicated as developers built parallel libraries for each toolkit.
So I think the answer is to launch a language without the kitchen sink, but watch the community and gradually standardise useful functionality as the need emerges and adapt popular open source libraries as they becomes popular. Java did this well in its heyday. In JS's case, a lot of the DOM conveniences are now becoming core JS, but the nature of JS means libraries move slower than other languages.