Okay, duh. The license information was staring right at me on their homepage:
"ICU is released under a nonrestrictive open source license that is suitable for use with both commercial software and with other open source or free software"
Are we okay with including it in our stuff?