Are users always asked to accept application permissions? Does the Android OS always ask a user to review an application's permissions if it is not downloaded from the Android marketplace directly? For instance, downloading an application from a non-Google Android marketplace or directly from a website or computer. I could not find any information about this If so, please provide a documented occurrence or source.
No, or at least not in a way that can't be automated away.  Titanium Backup can install apps without the user seeing this prompt, for example.  It may require root to do this.

Without root, only the system can access the areas needed to install apps.  So barring any bugs, apps can only be installed by the system and the system will show the permissions if the Market has not already.  I don't have documentation of this, but the source code is freely available :P

Edit: Eldarerathis points out the AOSP security page, which indicates that the permissions dialog will be presented on app install, although adb install does not require this (presumably because you have physical access to the device in that case).  This is also confirmed by another official resource that sbaskin89 found.