If a country has a positive savings rate, that means that more money had to come into the country from somewhere outside of the country. However, we run a trade deficit, so we're actually sending more money out than we are bringing in. How is this possible?
Premises of your Q are simply false:
If a country has a positive savings rate, that means that more money had to come into the country from somewhere outside of the country.
This is completely incorrect. Total savings of a country is sum of private and public saving. For an open economy output is given by $Y=C+I+G+X-M$ (where $Y$ is output $C$ consumption $I$ investment $G$ gov spending, $X$ exports and $M$ imports, the private saving is $S_p=Y-C-T$ and public saving is $S_g=T-G$ (see Blanchard et al Macroeconomics a European Perspective). Thus we can clearly see that $S_p+S_g=I+X-M$. In another words in open economy public and private saving must be equal to investment plus exports minus imports.
Let us suppose investment is 1000 exports are 0 and imports are 500 thus trivially country runs trade deficit yet has positive saving of $S_p+S_g = 1000+0-500 = 500$. Trivially saving is possible.
In addition, country having trade deficit is not equivalent to country sending out money. Generally you can only use home currency in your home country. Generally speaking one cannot use Japanese yens in the UK. If Japan wants to import cars from UK it has to sell its yens and buy pounds. Yens will be purchased by people who want to buy something in Japan because yens can be generally used to buy stuff etc only in Japan. So the total number of yens in Japanese economy will not change just because of trade deficit vis-a-vis UK, the same way as money supply of pounds in UK will not increase just because UK is running trade surplus vis-a-vis Japan.