This question was way back and hence i would like to update the info. There is a definitely a direct UPS integration with Shopify which can be found from here which is operational for USA customers.
As far as FedEx is concerned, Shopify has not yet provided any integration with FedEx. However, with the Multi Carrier Shipping label app you can put your own FedEx account details inside the app and start shipping from within your Shopify store. It automatically calculates shipping rates at checkout and also automatically generates labels for you. And once you have an account with FedEx, the app can be operational throughout the world.