Absent specific statements about the deal, the refugees are subject to the same rules as "normal" refugees, since the Nauru isn't some special source of refugees, but merely an offshore detention center where Australia sends all boat-bound refugees trying to get to Australia.
As such, how they are treated visavi Trump's order, would depend on where they are from. Current reporting (which isn't based on the actual order, so may change) lists the order as being restricted to refugees from Syria, Iraq, Iran, Libya, Somalia, Sudan, and Yemen.
As such, if the refugees detained by Australia in Nauru and Papua New Guinea are from those 7 countries, they would be subject to the new order. Otherwise no.
There's no exact statistics on Narau refugee origins but my impression is that many would fit the ban, but not all - for example, the original crisis that led to narau detentions (MV Tampa) was about refugees from Afghanistan that isn't on the list. Wiki has very vague:
Many detainees have since been returned to their countries of origin, including Iraq, Syria, Somalia, Sudan, Afghanistan and "unknown" destinations
Caveat: Obviously, the whole thing is entirely within Executive Branch. So, there's nothing that says the administration can't say "Oh, and this order doesn't apply to Australia deal, at all". I'm not aware of anything like that happening at the moment, and it's unlikely based on general ideas behind the order; but only time will tell conclusively.
