Does Cisco IOS NAT support inbound translations on a Frame Relay interface? Does it support outbound translations on the Ethernet side?

Yes. Encapsulation does not matter for NAT. NAT can be done where there is an IP address on an interface and the interface is NAT inside or NAT outside. There must be an inside and an outside for NAT to function. If you use NVI, there must be at least one NAT enabled interface. See How do I configure NAT?for more details.