Much depends on your scenario.
If the two hosts collaborate, just have one of the two send its IP to the other. Optionally hash/encrypt it in order to keep protocol rewriting filters (such as ftp-masq) from rewriting not only the header packet IP but the payload too. Then, if the two addresses don't match, NAT must have been at work.
If you only have one host, that for example connects to your host, and want to know whether it's a 'true IP' or a natted IP, you probably won't be able to -- if the connecting machine is expected to have some service available, you can try connecting to its corresponding address and port; unless the NATting machine is also doing reverse masquerading / "virtual server" translation, you should be able to see whether the service is open on the requesting machine (no NAT) or not (NAT).
With several hosts, you could be able to count packets and exit ports of incoming connections. NAT boxes and "ordinary" boxes have different port assignment schemes. Traffic asymmetries from different source ports may also be symptomatic of NAT (or someone keeping several web pages open onto a proxy; how likely that is, depends on the scenario. Two port pairs having both usually-interactive traffic of a wildly different kind are likely due to there being two users behind a NAT. And so on).
Another approach could be to inspect packet timing and TTL. Usually NAT implementations do not reset TTL counter, so it will be decreased by one when NATting. NAT takes a little time too, and this can be statistically investigated.
Finally you could try being sneaky and reply with forged packets, again playing with TTL. If the NAT box is regenerating TTL to hide its NAT, chances are that it will do so only for outbound packets, and rely on normal code for inbound traffic. If you send a packet with TTL crafted to "expire upon impact", a non-NATted machine will still receive it. The NAT box will receive it, decrement TTL counter, and the packet will die in transit without reaching the originating machine. You will either get a drop or a TTL-Exceeded ICMP reply.
Sometimes, similar strategies may be employed with packet fragmentation schemes, but this requires the remarkable luck of having an asymmetrically favourable MTU configuration in the "legs" from your machine to the supposed NAT box, and from this to the real machine.