Salesforce REST API call into Force.com platform requires OAuth 2.0 authentication. OAuth is an industry-standard authentication mechanism using "tokens" instead of a typical "username" and "password" credentials. OAuth access tokens provide permission to make Salesforce API calls, and do not grant permission to login to Salesforce Web UI.

1. Navigate to Connected App on Salesforce UI.
Setup -> Build -> Create -> Apps -> New Connected Apps.

2. Create a new Connected App

3. Locate your Client ID (Consumer Key) and Client Secret (Consumer Secret).

4. Since setting up an OAuth for the first time may require significant resource, we'll use the Username/Password shortcut method. Generate a token via command-line.

% curl https://test.salesforce.com/services/oauth2/token
    -d "grant_type=password" -d "client_id={Consumer Key}" 
    -d "client_secret={Consumer Secret}" 
    -d "username={Salesforce Username}" 
    -d "password={Salesforce Password}"

{"id":"https://test.salesforce.com/id/00D19DgrIEAS/AAA..",
"issued_at":"1414428409107",
"token_type":"Bearer",
"instance_url":"https://cs24.salesforce.com",
"signature":"c0EhPphArd3IKQwu8...",
"access_token":"vMr5LUNIuPwzosl..."}

Debugging REST Web Services

The best way to test your web services is to use Workbench with the Salesforce Debug Logs. The browser based workbench does not require OAuth as long as your browser session is active. To view Debug Logs, you'll have to create a Debug Log under your Salesforce user account.

Setup: Create a simple Apex class serving REST-based Web Service

@RestResource (urlMapping='/wte/test/*')
global class WTE_SampleRESTService {
	@HttpGet
	global static void doGet() {
		String id = RestContext.request.params.get('id);
		System.debug('ID: '+ id);
	}

	@HttpPost
	global static void doPost(String id, String name) {
		System.debug('ID: '+id+', Name: '+name);
	}
}

1. Create a debug log for a user. Login as a System Administrator to Salesforce.com.
Setup -> Monitor -> Log -> Debug Logs -> New

2. Log into workbench.

As stated on the Salesforce documentation, on the POST and PATCH transactions the JSON/XML name field must match Apex parameter name in the method signature.

If you receive "Session expired or Invalid (INVALID_SESSION_ID)" from your Rest API, you'll need to verify the following:

1. Ensure that the API user has the API access in the user/profile. Go to Setup -> Manage Users -> Profiles -> {API User Profile} -> Administrative Permissions. Ensure API is enabled.

2. Ensure that you have the correct Endpoint URL. If you rebuilt the Sandbox, you may have to edit your endpoint URL. To whitelist your IP, go to Setup -> Security Controls -> Network Access and add a new IP range.

3. Ensure the IP invoking the API has network access to the Salesforce account.

References:
Interact with the Force.com REST API from PHP
Salesforce Workbench - REST Explorer
Digging Deeper into OAuth 2.0 on Force.com
Force.com REST API Developer's Guide