From Azure's site:
Relay
The Service Bus Relay service enables you to build hybrid applications
that run in both a Windows Azure datacenter and your own on-premises
enterprise environment. The Service Bus relay facilitates this by
enabling you to securely expose Windows Communication Foundation (WCF)
services that reside within a corporate enterprise network to the
public cloud, without having to open up a firewall connection or
requiring intrusive changes to a corporate network infrastructure.
Relay also handle load balancing for you (you can have multiple applications listen at the same endpoint for the majority of the bindings).
Brokered Messaging
The second messaging solution, new in the latest release of the
Service Bus, enables “brokered” messaging capabilities. These can be
thought of as asynchronous, or decoupled messaging features that
support publish-subscribe, temporal decoupling, and load balancing
scenarios using the Service Bus messaging infrastructure. Decoupled
communication has many advantages; for example, clients and servers
can connect as needed and perform their operations in an asynchronous
fashion.
Brokered messaging includes Queues and Topics / Subscriptions that allow you to send / receive messages asynchronously.
The main difference is that for relay, you have applications listening at an endpoint. When you send a message, the application processes that message when it is received. For brokered messaging, the message is stored when it is received by the client and can be processed at any time.