Please note that I can't be held liable for any errors or omissions in the document and you will need to seek real immigration lawyer should you have any questions not answered on the USCIS/SSA websites.
TL;DR version: get EAD then SSN and that's all the documents you need to start working.
L-2 is a visa type/status issued to "a spouse of intra-company transferee". Regardless of what you read elsewhere you are NOT eligible to work anywhere unless you receive an Employment Authorization Document.
For some weird reason, SSA and DHS disagree on whether L-2 holders are eligible to work w/o EAD:
Spouses of L-1 workers may apply for work authorization by filing a Form I-765, Application for Employment Authorization with fee. If approved, there is no specific restriction as to where the L-2 spouse may work.
For COAs displaying a double asterisk (**) (non-immigrant E-1, E-2, and L-2 classifications), the spouse is also authorized to work without specific DHS authorization.
A person admitted under L-2 can obtain SSN w/o EAD, the list of documents is:
an EAD (Form I-766) showing “A-18” under Category; or
evidence other than an EAD that proves the L-2’s lawful alien status (e.g., I-94) and a marriage document as evidence that he or she is the spouse of the principal L-1 alien.
However, in my case I was specifically asked for an EAD while submitting the documents for SSN, stating that otherwise I would not be eligible for receiving SSN, your mileage may vary.
Based on the DHS documents, your employer will want to see the work authorization and the I-9 form states that SSN showing "ALLOWED TO WORK ONLY WITH DHS AUTHORIZATION" is not enough.
Employment Authorization Document is issued by Department of Homeland Security. While you can eFile the documents, you will still need to provide a payment (personal check or money order) and photos, so you will need to get these to the USCIS (U.S. Citizenship and Immigration Services) and the easiest way is to mail everything using the post office.
You will need to figure out where you need to send the documents based on the state you are currently in, see the instructions for your I-765 form.
A completed I-765 form, Application for Employment Authorization.
2 passport-sized photos on white or off-white background - 2"x2".
A Personal check or money order for $380 payable to "U.S. Department of Homeland Security" (not "USDHS" or "DHS"). (check the fee at I-765 form page). You can take the photos ($15.00) and purchase a money order at the Post Office ($1.20 fee in my case). Since you will want to send the documents via the Priority Mail with tracking number, you will want to go to the post office anyway.
A copy of your passport identification page and L-2 visa.
A copy of your spouse's passport identification page and L-1 visa.
I-94 information - you can print it from Admission (I-94) Number Retrieval page.
An authorized translation of your marriage certificate (it is not mandatory to be notarized, anyone other than you can perform the translation, adding the footer mentioned in the Translation of Non-English Documents for U.S. immigration purposes page.
Double and triple-check the contents of your mail prior to posting. Create a checklist and tick it off as you put the items into your mail, you really want to get everything done properly from the first time.
You will want to get a tracking number, so that you will be able to check the status of the message as it is traveling through the US to the lockbox facility.
Once USCIS receives your mail and checks that it is intact, you will receive a mail message, Form I-797C, Notice of Action, where you will see the current status of your case and the receipt number.
Now go to USCIS, create an account and register for e-mail notification as your case passes various stages.
When your application is approved, DHS will send you another I-797 Notice of Action, this time on a fancy watermarked paper stating that your card is being sent to you.
Here's how the card looks:
If you signed up for e-mail notifications on the case progress, you will also receive an e-mail containing the USPS tracking number, however in my case there appears to be a template processing bug, and I was left with "#DCN" as the tracking number. I have notified the webmaster about the issue, but haven't heard anything back yet.
Change of address
EAD processing may take up to 90 days, if you happen to relocate while you are waiting for the document to arrive, you can update the address online, specifying the receipt number you received in the first "Notice of Action". When DHS updates your information they will send you a paper mail notification about the same.