Deployed applications can depend on any package available on CRAN as well as any package hosted in a public GitHub repository.
When an application is deployed it's source code is scanned for dependencies using the appDependencies() function. The list of dependencies is sent to the server along with the application source code and these dependencies are then installed alongside the application.
Note that the Suggests dependencies of packages are not automatically included in the list of dependent packages. See the Note section of the documentation of the appDependencies() function for details on how to force packages to be included in the dependency list.
When sastisfying CRAN package dependencies, the server will build the exact versions of packages that were installed on the system from which the application is deployed.
If a locally installed package was not obtained from CRAN (e.g. was installed from R-Forge) and as a result doesn't have a version that matches a version previously published to CRAN then an error will occur. It's therefore important that you run against packages installed directly from CRAN in your local configuration.
It's also possible to depend on packages hosted in public GitHub repositories, so long as they are installed via the devtools::install_github() function from the devtools package.
This works because install_github records the exact Github commit that was installed locally, making it possible to download and install the same source code on the deployment server.
Note that in order for this to work correctly you need to install the very latest version of devtools from Github. You can do this as follows:
library(devtools)
install_github("r-lib/devtools")