Assume JOB_ID is ID of existing job.

POST /api/jobs/JOB_ID/steps/
<step>
  <description>Test Step</description>
  <type>EXECUTING</type>
  <status>
    <state>FINISHED</state>
  </status>
</step>

POST response = step created with state STARTED
<step href="/api/jobs/JOB_ID/steps/NEW_STEP_ID" id="NEW_STEP_ID">
    <actions>
        <link href="/api/jobs/JOB_ID/steps/NEW_STEP_ID/end" rel="end"/>
    </actions>
    <description>Test Step</description>
    <job href="/api/jobs/JOB_ID" id="JOB_ID"/>
    <type>executing</type>
    <number>0</number>
    <status>
        <state>STARTED</state>
    </status>
    <start_time>2013-07-24T16:59:37.061+02:00</start_time>
    <external>true</external>
</step>

New step always put into STARTED state actually makes sense.

But if I omit <status> from POST request, I'll get following fault: Step [status.state] required for add

This makes <status> required in POST request but it doesn't seem to have any effect.