Cross-Object Workflow in Salesforce.com

With Spring '12 release, cross-object field update in workflow rules and approval processes is now support standard objects. Both custom-to-standard and limited standard-to-standard relationships are supported. This feature only available in Enterprise and Unlimited edition.

Only Master-Detail relationship support for cross-object workflow, so it is not for objects with Lookup relationship.

Here is a sample case of using Cross-Object workflow.
Master object: Customer__c
Child object: Order__c
Company would like to know how total amount and when latest order for each customer, use payment date instead of order date. Payment date will be blank when customer have not make payment.

Here we go:
1. Create a workflow in Order 
Evaluation Criteria : Evaluate the rule when a record is created, and every time it’s edited
Rule Criteria:
NOT ISBLANK( Payment_Date__c ) && 
( Payment_Date__c >= Customer__r.Payment_Date_hidden__c || 
ISBLANK( Customer__r.Payment_Date_hidden__c ))

Explanation:
- if Payment Date in order is blank, stop workflow
- if Payment Date in order is newer than stored Payment Date in customer, proceed workflow OR if stored
Payment Date in customer is blank

2. Create a field update action in Order
Update Payment Date in Customer
Select object = Order
Field to Update = Customer, the select field Payment Date
Formula Value = Payment_Date__c from Order

3. Create a Roll-Up Summary field in Customer for Total Amount
Create new Roll-Up Summary field from Customer object
Summarized Object = Orders
Select Roll-Up Type = SUM
Field to Aggregate = Amount
Filter Criteria = Payment Date NOT EQUAL TO blank

Last one, remember to Activate the workflow.

If you see in above process, workflow in Order will update field in the parent object Customer. So, it is cross-object workflow field-update.

The same solution you can use to update Account from Opportunity, example: if opportunity is Closed Won, automatically update Account Type to Customer.

For more information and standard objects supported, see this release document and find section Cross-Object Workflow. 

Reference: Understanding Cross-Object Field Updates