es5-shim, as you rightly mentioned, adds some JavaScript functions like map, reduce, some and forEach on Array if the browser's JavaScript engine is not ES5 compatible. Underscore.js adds utility methods similar to the above (and more) within the "_" namespace. So, in this case, using both in the same application is redundant.
That said, es5-shim, adds a few more functions like Date.now, Date.toJSON, Function.bind, String.trim (and more) some which don't have direct equivalents in Underscore.js. For example Underscore does provide _.bind and _.bindAll that is equivalent to Function.bind, but Underscore.js does not provide Date.now and Date.toJSON.
So, if you use these additional methods provided by es5-shim you can stay with both es5-shim and Underscore.js in your application. But, if you are not using these additional methods, then using es5-shim would just be an unnecessary increase in application size and waste of bandwidth.