Hola,se puede hacer con una api llamada
SystemParametersInfo,algo asi Declaras:
Private Declare Function SystemParametersInfo Lib "user32" Alias "SystemParametersInfoA" (ByVal uAction As Long, ByVal uParam As Long, ByVal lpvParam As String, ByVal fuWinIni As Long) As Long
Const SPI_SETDESKWALLPAPER = 20
Const SPIF_UPDATEINIFILE = &H1
Const SPIF_SENDWININICHANGE = &H2
y despues la usas asi:
Dim Ruta As String
Dim ret As Long
FileName = "c:\foto.bmp"
ret = SystemParametersInfo(SPI_SETDESKWALLPAPER, 0&, Ruta, SPIF_UPDATEINIFILE Or SPIF_SENDWININICHANGE)
y si queres vos mismo elegir la foto,pones un control commondialog o con la api como quieras para mostrar la ventana de abrir archivo y despues la variable que retorna la ruta de la imagen seleccionada,la igualas con la variable FileName..
saludos.