What can you recommend for an almost complete beginner?

My main setup is Win 7 64, though I could comfortably manage any linux as well. I also have access to OS X / XP, so plenty of choice..

I have done basic things before like in 2000, using krobars/fravias tuts, and knew basic assembler and used softice, hex workshop on WinME...

What's good these days?

You can start by reading the FAQ ("http://www.woodmann.com/fravia/rce-faq.htm").

That's a pretty broad question not knowing your background knowledge or interests, but one of the first things might be to set up a Virtual Machine with XP as a working environment. As targets, reversing malware will give you all the challenge you can handle, as well as marketable skills if you want to go beyond the hobby stage. Solving Crackmes and following things like "Lena's tuts" are a good way to get the basics.

Learning the PE format, API's, basic programming, use of all the tools, etc. are part and parcel of it all. It's a never ending learning process no matter how long you've been doing it, so enjoy the ride.

There are virtually unlimited sources of information you can cull from, here are a couple

http://opensecuritytraining.info/IntroductionToReverseEngineering.html
http://opensecuritytraining.info/ReverseEngineeringMalware.html

Feel free to ask more specific questions if you wish.

I fully agree on XP as working environment: you will avoid a lot of nuisances, such as DEP, UAC, drivers signing, 64bit ramblings...
Best regards, bilbo

1. CPU: http://www.intel.com/content/dam/www/public/us/en/documents/manuals/64-ia-32-architectures-software-developer-manual-325462.pdf

2. PE COFF: http://msdn.microsoft.com/en-us/library/windows/hardware/gg463119.aspx

3. WRK: http://habrahabr.ru/post/88548/ + "NT_Design_Workbook" -necessary!
(& Windows 2000 Source code) - private.
http://www.reactos.org/

4. Possibly Windows Internals(http://technet.microsoft.com/en-us/sysinternals/bb963901.aspx).

5. Use Masm32 pack(dont use fasm!), I recommend start with PB(http://www.purebasic.com/) - make /COMMENTED opt. & ollydbg

6. Start with native subsys.(ntdll).